Weird: Different results just by hitting "Start Compilation"

Is your design fully timing constrained? When it doesn't work, does it fail timing? You don't want to get to the point where determining if it works or doesn't work is done by running actual hardware. You really need all the timing constraints, and if it passes timing be confident that it will work in hardware. (And if it doesn't work, debug why, which usually leads to something invalid in the design or the timing constraints).

As for whether the design re-uses anything on the next compile. The general answer is no. If I want to check, I generally look at my setup slacks. If anything changed in the design at all, those values will be different. (If you don't have the previous compile, there's no way to tell).

- Incremental Compilation can cause different results compile to compile, under some very specific circumstances. Unlikely.

- There's a perpetual rumor of people getting different results, but it's been nearly impossible to track down. I've heard it enough that I assume it's true, but whenever we try to debug, the result is that a) the original compile with /db is no longer around and b) it can't be reproduced.

- I also know of a problem with the JTAG controller that caused this behavior. I believe it was in Quartus 12.0/12.1 and fixed in 13.0, but not positive on the releases. In this case, if you compiled without a /db you always got result A, and if you compiled with the /db you always got result B(you could re-compile as many times as you wanted and get B). Looking through the hierarchies, it was the jtag logic that changed sizes. Basically the JTAG logic puts an ID into the device to link to the image. This is used by many of the JTAG functions that are run on a computer(SignalTap, SystemConsole) to make sure the image in the FPGA matches the SignalTap image, etc. It was pulling something out of the /db to calculate this ID, which was incorrect.

Though you should get the same results on each compile, I can't stress how much having proper timing constraints is, and therefore even if it's a different fit, as long as it passes timing it will work. Without this pass/fail test, it's impossible to tell what you put into hardware works across PVT.