Most Debian/Ubuntu admins I know use aptitude these days, rather than apt-<tool> directly.
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.