While doing regular system maintanance with eix one notification looked not as regular:

user@host % eix-test-obsolete quick

No non-matching entries in /etc/portage/package.keywords
No non-matching entries in /etc/portage/package.accept_keywords
No non-matching entries in /etc/portage/package.mask
No non-matching entries in /etc/portage/package.unmask
No non-matching or empty entries in /etc/portage/package.use
No non-matching or empty entries in /etc/portage/package.env
No non-matching or empty entries in /etc/portage/package.license
No non-matching or empty entries in /etc/portage/package.accept_restrict
No non-matching or empty entries in /etc/portage/package.cflags
The following installed packages are not in the database:
x11-proto/inputproto
x11-proto/xextproto
x11-proto/xproto

Running eix for search of a particlular package reported the same:

user@host % eix x11-proto/inputproto
No matches found

Asking in the official #gentoo IRC channel at freenode brought up more interesting portage commands, on how to search for orphans

user@host % emerge -cpv x11-proto/xproto

Calculating dependencies                ... done!
  x11-proto/xproto-7.0.31-r1 pulled in by:
    x11-wm/fvwm-2.6.7 requires x11-proto/xproto

>>> No packages selected for removal by depclean
...

The usage of the command emerge -c (depclean) -p (pretend) -v (verbose) orphan-package/name is really great in that example. Since it pinpoints the source of the issue. At that point it is necessary to rebuild the package here x11-wm/fvwm-2.6.7. And after that rebuild the dependency should be gone. If it is not gone you either hit a bug, or this ebuild causing this is from an overlay, which could be not well maintained.

Also emerge displays a hint what would be the correct action in such a case:

 root@host % emerge -C =x11-proto/xproto-7.0.31-r1 =x11-proto/inputproto-2.3.2-r1
 * This action can remove important packages! In order to be safer, use
 * `emerge -pv --depclean <atom>` to check for reverse dependencies before
 * removing packages.

It is always a good to have the right tool at the right time, and to know how to use it. Gentoo's emerge is such a tool.