Quartus II Fitter advice

It is very unusual to need to overconstrain the timing requirements or to get a benefit from overconstraining. If you get an apparent benefit for one compile, that might be a random change in result not related to the change in the requirements.

If "Fitter effort" is set to "Standard Fit", the Fitter should be giving the best fmax it can regardless of the requirement. For a design with one clock domain, increasing the fmax requirement should make no consistent difference in actual fmax (no difference on average over a seed sweep or for multiple compiles done for other small changes).

For a design with more than one clock domain, artificially overconstraining one domain could make the Fitter work harder on that domain compared to other domains. If that's what you want to do, it would be better to overconstrain with clock setup uncertainty and keep the frequency requirement in Quartus set to the true frequency requirement of the design.

If "Fitter effort" is set to "Auto Fit", the Fitter estimates when it has gotten good enough performance and then stops optimizing. If "Auto Fit" gives negative slack and a Fitter compilation message says that some performance optimizations were skipped, then the Fitter probably made a wrong decision. It would be good to file a service request and let Altera look at the design. For your own immediate solution, you can add some guard band to this "Auto Fit" early-termination-of-optimization decision by enter a value for "Desired worst case slack (margin)" in the dialog box for Fitter Settings, or you can simply change to "Standard Fit".