This is one of the reasons I jumped ship from writing VHDL for Xilinx parts and am now a Java dev. It’s worth noting that Altera, the other major FPGA vendor, is not noticeably better in this regard (or at least they weren’t when I last used their stuff ~5 years ago).
(The other reason is that I am unbelievably bad at getting the damn thing to meet timing.)
Not with the same exact source files / same software version. But sometimes small changes in the design, or changing tool versions can cause the design to not meet timing. It's just the nature of map / place and route.
It often is. Place-and-route is typically implemented as simulated annealing, which is a randomized algorithm. Unless you explicitly force it to reuse the same seed, you'll get slightly different results each time -- and even if you do set a seed, small changes to the HDL may result in a vastly different result.
(The other reason is that I am unbelievably bad at getting the damn thing to meet timing.)