Also on ~amd64, I now also have same result from dev-lang/icc-11.1.046-r3 as Stephan Friedrichs above (but not using paludis), revdep-rebuild always returns:
Configuring search environment for revdep-rebuild
* Checking reverse dependencies
* Packages containing binaries and libraries broken by a package update
* will be emerged.
* Collecting system binaries and libraries
* Generated new 1_files.rr
* Collecting complete LD_LIBRARY_PATH
* Generated new 2_ldpath.rr
* Checking dynamic linking consistency
broken /opt/intel/Compiler/11.1/046/bin/intel64/iidb (requires libDebuggerData.so libDebuggerServices.so libPostOffice.so libScheduler.so libxerces-c.so.27)
* Generated new 3_broken.rr
* Assigning files to packages
*   /opt/intel/Compiler/11.1/046/bin/intel64/iidb -> dev-lang/icc
* Generated new 4_raw.rr and 4_owners.rr
* Cleaning list of packages to rebuild
* Generated new 4_pkgs.rr
* Assigning packages to ebuilds
* Generated new 4_ebuilds.rr
* Evaluating package order
* Generated new 5_order.rr
* All prepared. Starting rebuild
emerge --oneshot --pretend dev-lang/icc:0

These are the packages that would be merged, in order:

Calculating dependencies... done!
[ebuild   R   ] dev-lang/icc-11.1.046-r3
* Now you can remove -p (or --pretend) from arguments and re-run revdep-rebuild.

The path declarations in /etc/env.d/05icc (identical to /etc/env.d/05ifc) look OK:
PATH="/opt/intel/Compiler/11.1/046/bin/intel64"
LDPATH="/opt/intel/Compiler/11.1/046/lib/intel64"
LIBRARY_PATH="/opt/intel/Compiler/11.1/046/lib/intel64"
NLSPATH="/opt/intel/Compiler/11.1/046/lib/locale/en_US/%N"
MANPATH="/opt/intel/Compiler/11.1/046/man/en_US"