Earlier today, I noticed - in htop - that a particular process, let's say 'foo-123', was running even though I had removed the package 'foo' many days earlier. I tried removing it again and found that I was right and that the package had already been removed. The package dependency list was way too long for me to go removing them one by one, or parsing them out and removing the lot.
IRC, however, was very obliging to my query and provided me with the below-pasted nifty solution that did not allow any odd gimmickry:
sudo aptitude search '~i' | grep foo
aptitude search in the above command will list all installed packages - prefixed with an i - including automatically installed packages which are additionally prefixed with an A. The
grep filters these results to only display the packages that I was interested in, namely those containing the strong foo.
Once I located the offending package, it was a simple matter to get rid of it.
Game, Set and Match :)