The stack traces show that AbstractTestResultAction.findCorrespondingResult() indirectly calls itself recursively, and in these cases that recursion has caused a StackOverflowError.
From Stefan Thurnherr's description, this sounds like it may have a similar cause to https://issues.jenkins-ci.org/browse/JENKINS-33168?focusedCommentId=285979&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-285979 - where StabilityTestDataPublisher.buildUpInitialHistory() iterates through many failing tests, getting their previous results across multiple builds. When memory pressure is high (eg lots of build history), CaseResult.getPreviousResult() can't use its WeakReference cache and has to load results from disk, thus loading each build's results many times instead of once. And now it's apparent that this involves calling AbstractTestResultAction.findCorrespondingResult() recursively for every previous build.
So there are two related problems here:
1. When loading results with lots of history, the recursion in findCorrespondingResult() causes a StackOverflowError unless (a) previous results were found in the WeakReference cache or (b) the number of previous results fits in the stack. (Will Harris's binary search from the earliest build mitigated this by preloading a limited number of results into the WeakReference.)
2. Test Stability Plugin calls findCorrespondingResult() a lot when building initial history for a failing test. This produces a lot of memory pressure when there is a lot of build history, thus defeating the caching in 1(a) above. (In JENKINS-33168 the number of builds apparently hasn't been high enough to overflow the stack, but the number of test results is too much for the cache, thus killing performance.)
So increasing stack size should certainly work around the StackOverflowError unless the number of builds gets too high, but if you use Test Stability Plugin you will probably encounter JENKINS-33168 if you have a lot of builds with a lot of tests in them.
I think AbstractTestResultAction.findCorrespondingResult() in the JUnit plugin (or something else in that recursive call stack) needs to be redesigned to avoid recursion, otherwise a StackOverflowError is unavoidable when there are a lot of previous builds. (Solving JENKINS-33168, on the other hand, will require iterating in such a way that each build's results are only loaded once.)