Random results in timing closure

The Fitter will use the timing specs to try and create a design that will meet timing, but at some point, it will just give up. Timequest is nothing more than an analysis tool to help you debug where the fitter was having difficulty. The randomness you see is perfectly expected. The fitter uses a seed (based on the source code and fitter seed) to start the fit process. Using a different seed will produce a completely different layout.

The best and easiest way to fix timing problems is to change the RTL. What are the timing problems? are they through logic between flops, or at the IOs?

If it is your design, they increasing pipelining (reducing logic between registers) will make the fitter's job easier.

Also - have you specified all false paths/multi-cycle paths correctly? getting these set correctly reduces the effort the fitter needs to make and means it can put more effort in elsewhere in the design.