Every package in the store has exact dependencies - they reference the hashes of other packages only. When a package is built with Nix, only the directories for these packages are exposed to the chrooted environment in which the build occurs - so it is simply not possible for some randomly added junk in the filesystem to make it's way into a nix-defined package.
Contrast this to building software on another machine, where I might depend on "glibc" version "1.0". The combination these two values hardly represents a unique identity, as I could make any random package that fits those requirements. It's much more difficult for me to create a package which results in an hash collision though.
One thing that makes the other systems so unreliable is the presence of multiple repositories. If you were going to deploy packages from a single repository, then you can do careful planning in such a way that packages do not have any collisions. Assuming no user mutates the directories under control of the package manager, such system will also be effectively reproducible. Current mainstream distros work surprisingly well because they basically use this model, where a default repository provides most users needs. These distros quickly break down when you start adding third-party repositories which bundle alternative compilations of the same software that sits in the "official" one.
Basing packages from hashes (identity), rather than names and numbers, and making sure all of the files for each package is held in an isolated directory ensures that collisions won't happen, even if two different repositories provide the same software name and number, they are represented by different hashes, and will be treated as distinct pieces of software.