How do you eat an elephant? One bite at a time. It sounds you are looking for a "magic bullet" to solve all of your problems at once, and that's IMHO part of the problem. There is not magic bullet, this is hard work, and you can only solve it step-by-step.
For example, you told us that you have already some fuzzy or statistical methods in place to compare the result of your tests to an expected result. I guess these fuzzy methods have some threshold parameters when to accept a result and when not. Whenever you change the behaviour of your algorithms, you will have to adept these parameters - do this for one change after another, run the tests again, make sure the new results are in the accepted range. In fact, you have to fine-tune this parameters, since it may be not ad-hoc clear which results are correct, which are incorrect and if there is a "grey area" between right and wrong.
If that does not work, you may have to look for a modification of the "fuzzy comparison" itself - each time you come across a new kind of change. Unfortunately I cannot tell you how these comparison have to look like, since one must have in-depth know-how about your problem domain to make a right decision.
And if this does not work either, this may also be a sign that your modification of the algorithm introduced too many unwanted side effects, so maybe you don't have to change the test, but the way you modify the algorithm implementation.
I have had many ideas, but they don’t work for all cases
Then don't look for a solution which works for "all cases". Use different solutions for different test cases.