How can I "clean house" so that dpkg -l no longer lists packages I've removed?

Run

sudo dpkg --purge <package>

or

sudo apt-get purge <package>

to uninstall <package> AND its configuration files.