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.