For multithreaded tests it may also be worth investigating byteman as this can make the concurrent execution of the code deterministic.
Of course it will still require an analysis of the codebase to determine the appropriate tests but the determinism could be worth the time spent.