On my system, "man gcc" works fine, but "man -k gcc" results in "gcc:
nothing appropriate.".

It looks like there are two implementations, so I'll note that virtual/man
is currently being satisfied by sys-apps/man-db.

Before I list everything I've already checked and tried, does anyone
immediately recognize this issue? Can anyone else reproduce it?

I'll preempt one obvious suggestion:
$ ls -l /var/cache/man/index.db
-rw-r--r-- 1 man man 2666496 Oct 31 18:45 /var/cache/man/index.db

Thanks all,
-MD