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