The worst was that some tests were actually wrong and only passed due to nondeterminism. Once I made the tests deterministic, I discovered they always failed. Until that point, I found those test failures very confusing, because it seemed like my efforts to improve the reliability of the tests was having no effect on them.
The test dealt with a "week", and on Saturday evening, the current week in UTC differed from that of the local timezone.
* The test cases written by the some guy who left the company are now your test cases.
* Before he left the company, he was able to commit the test cases, passing whatever review / quality processes were put in place by the company (or that the company failed to put in place).
* If your team wants to have the benefit of reliable testcases, the knot needs to be untangled. That doesn't entail "dropping everything" (although perhaps thats the only way your organization knows how to operate), there is no reason that improving test cases can't be prioritized alongside and in the context of other work.
Unfortunately, in my experience it's usually the last bullet point where things fall down. Product owners consistently pressure development teams to deliver features now, and do test cases later, which means never.