I just happened to realize that I have 7,000,000 files in a 2GB CCache. That cache was indexed on a daily basis which took quite long. After excluding /root/.ccache updatedb runs only a couple of seconds. I think ccache is used quite frequently on gentoo systems. BTW: It would be nice to have something like ~/.ccache and ~/.maildir etc. which excludes those directories in all homes. No idea how to do that (at least /*/.ccache did not work).
I added /root/.ccache, no revbump. Currently slocate won't let you use wildcards. Adding support wouldn't be too tricky, but that's for a different bug.