The warning in fixpackages says it should run a couple of minutes, but a typical time of running it is more than an hour, sometime more than three hours. And that is on 4-way RAID-5 server! I would not complain about such a speed, but it's in average 30% chance that "emerge rsync" insist to run fixpackage by its end.
it says you should run fixpackages whenever a package has been moved in the portage database
Well, "emerge rsync" advises to run fixpackages almost every other time. 3 hours for fixpackages each time after that makes me to think that I shoud run "emerge rsync" not more often than once per week, right? It might be ok for a conservative end-user, but it's not exactly convinient in a development environment.
Spanky, it doesn't matter how often you run fixpackages, it's always scanning all binary packages for broken dependencies. See bug 28704 for a little analysis.
genone's speedup was added. It should be better. You can run it whenever you like. You don't have to run it every other time. It only affects binary packages.