Aptitude handles package removal, especially orphaned dependencies much better. I think it's now included in the Debian base system, so there's very little reason to prefer apt.
Also, I usually use deborphan to find orphaned packages and remove them, if apt-get autoremove didn't find them.
I guess I could keep using apt-cache for searching and aptitude for installation/removal though.