Exact recreation of Xilinx FPGA binaries from source control
I used to work in a job that had a contract requirement that we could reconstruct our integrated circuit designs and simulations for twenty years. That was a battle we fought over and over again, so I have had some experience with the painful process of "archiving" a complex design.

1) If the design has tight timing constraints then it may be necessary to synthesize/optimize a number of times before all of the timing issues are uncovered and the timing constraints are "fully and correctly specified" as Dave Tweed puts it. This is particularly true if you incorporate any third-party IP, or if the person doing the synthesis is not the author of the HDL.

2) While the synthesis process is deterministic it is also subject to a vast number of variables. Some of these are hidden from the user. While I would say you should be able to get the same binary if you run exactly the same tools on the same computer on the same HDL with the same constraints on the same day, I would be hesitant to guarantee that any given binary could be reproduced exactly next week.

3) This is most certainly true. New versions of the design tools routinely break existing designs. It's not about some seed for a random number generator, it's about changes in the optimization algorithms and changes in the characterization data of the physical part. Because these changes are proprietary information they are largely hidden from the user and can appear to have a random nature.

4) This is typically true. The binary bitstream is the end result of the entire synthesis and optimization process. Most vendors hide the format of this data and may even encrypt it, which is why you can't find open-source FPGA design tools that go all of the way to the chip.

5) Is there ever any reason to store the NGC? I'll turn that around: can you justify that there is no information whatsoever in the NGC that cannot be obtained from whatever you are calling the "final design"?