If packages are merged and unmerged in somewhat strange orders it appears that they leave big messes all over /var/db/pkg which leads to problems with pkg-clean and other tools. What appears to happen is that under (exact circumstances unknown) certain conditions packages (for instance gimp-1.2.3-r1) will leave pkd-db entries under (for instance gimp-1.2.3) a higher level version deffinition, this confuses qpkg, pkg-clean and other tools.
this is probably due to a beta of Portage that was on your system. I don't think it's an actual portage bug. We had a portage that behaved this way for a while.
that could be... I wish I had noted the mtimes on stuff before I cleaned up the mess in /var/db/pkg what a waste of but #1000 ;-)