After some thinking about the GC process, we believe we have a fundamental problem with our approach. We execute our Nix builds from Docker containers. The approach is pretty much identical to what is outlined here in the NixOS Wiki.
These containers have access to the host Nix daemon and store, because they are mapped into the container. Now the problem is that a GC root from the container will actually be a non-existent path in the host system. That means if the build from the container tries to register a path, it will do so with its local chroot path name. The Nix daemon then presumably ignores/removes GC roots that point to non-existent paths.
So the solution is to not use Nix from inside Docker. 
Or at least try to configure the GC to not coincide with build jobs.