I was trying to install mozilla-firefox-bin 2.0.0.1 after a fresh 2006.1 installation. When emerge was trying to install xdpyinfo, it failed with this error: .... checking for a BSD-compatible install... /bin/install -c checking for i686-pc-linux-gnu-pkg-config... no checking for pkg-config... /usr/bin/pkg-config checking pkg-config is at least version 0.9.0... yes checking for XDPYINFO... configure: error: Package requirements (xext x11 xtst) were not met: Package recordproto was not found in the pkg-config search path. Perhaps you should add the directory containing `recordproto.pc' to the PKG_CONFIG_PATH environment variable Package 'recordproto', required by 'Xtst', not found Consider adjusting the PKG_CONFIG_PATH environment variable if you installed software in a non-standard prefix. Alternatively, you may set the environment variables XDPYINFO_CFLAGS and XDPYINFO_LIBS to avoid the need to call pkg-config. See the pkg-config man page for more details. So I installed by hand recordproto and re-emerged xdpyinfo and everything went OK this time.
x11-libs/libXtst already depends x11-proto/recordproto (and xdpyinfo depends on x11-libs/libXtst).