CPU cycles are cheap. Every major distribution has a build server. Determining dependencies is easy with proper package manager. Rebuilding all binaries should be as easy as pressing one button, and not take more than a few hours.

> Rebuilding all binaries should be as easy as pressing one button, and not take more than a few hours

If only that were true. There are some packages which take hours to compile by themselves, even on beefy servers.

Out of curiosity, an example? The only programs I've compiled that remotely approach an hour are the Linux kernel, GCC, and ATLAS. The first two are so fundamental that there's no point in recompiling for security reasons (if your current version is compromised, you should assume the resulting binary from a recompilation to be compromised). ATLAS is a specialized package that can be replaced in common circumstances with faster-to-compile packages.

IIRC, you can go from zero to a complete desktop Gentoo system in 2-4 hours on an i7 desktop. But even this long is admittedly an annoyance most users would not want to endure on a regular basis for a modest increase in security. The main reason people use Gentoo seems to be configurability, not security.

> Out of curiosity, an example? The only programs I've compiled that remotely approach an hour are the Linux kernel, GCC, and ATLAS.

Don't know about GP, but I can think of a few more: KDE, OpenOffice, Firefox (that alone takes about 2 hours on my quad-core Phenom), Chromium.