Huge numbers of recovery failures - even though reset is on Global Clock Net

Physical synthesis, as you mention, may fix the problem, though it will greatly increase compile time. If you must use a global, you may want to see if you should be using a different clock control block. That insertion delay (the time to get to the clock control block) is pretty long (4.1 ns), so you should check to see if the Fitter selected the closest clock control block for getting the reset on the global clock.