A partir de 12.04 você pode apenas fazer
sudo apt-get remove --purge {packagename}
para pacotes que já foram removidos.
Isso fará todos eles em um comando nifty ...
dpkg --purge 'dpkg --get-selections | grep deinstall | cut -f1'
Skool antigo:
Se você quiser fazer isso visualmente: instale o Synaptic do Centro de Software e execute synaptic
. Você pode encontrar o que deseja remover na seção "Não instalado (configuração residual)".