In order to reproduce a given Debian package from scratch, one would need to track down long chains of historical versions of packages from sid. Due to circular dependencies, these chains probably snake back to the very first versions of Debian before the availability of snapshot.debian.org. It’s possible that human judgment could be used to break some chains at an earlier point by substituting different versions, but this goes outside the guarantees provided by Debian’s reproducibility.
Nix guarantees that every package is built with the specified versions of its dependencies, and so on recursively. Some more rebuilding is necessary to maintain this guarantee, but in exchange, it enables stronger notions of reproducibility that Debian can’t.
(The work at https://www.gnu.org/software/mes/ aims to minimize the needed binary seed to a human-auditable size, and should be applicable to Nix and Guix.)
I consider this to be one of the main drawbacks of these systems -- it assumes that every machine is build-capable. I do not want compilers installed on my production servers (nor would I want my RPi to attempt to rebuild half the world because the package server was down). I'm not sure how Nix handles this, but I'm pretty sure that's not possible with Guix.
It doesn't, fortunately. You can tell Nix to rely exclusively on the binary cache, or configure it to have 0 build threads locally and use remote builders.
For a server deployment, many popular choices don't have the server build anything, and in some cases it may not even have any users who are allowed to invoke `nix-*` or anything.
It's been there for 15 or 20 years. Also Debian has been doing reproducible builds before Nix.