I have put together a patch (currently testing on GitGitGadget) that at least fixes things for my repo - Commits from before subtree add are recognized as a dead end, so it no longer runs out of stack space while finding its way to a root commit. I think the issue Marc ran into is a bit more complex in that the recursion eventually producing the wrong result suggests that correct identification of mainline commits remains an issue. While I have some ideas on how to improve that, it’s probably best handled separately. However, there is a decent chance that excluding a large number of known irrelevant commits will catch the problematic ones in that scenario - and should match the previous behavior of treating the problem commits as initial.
