Algumas aplicações criam arquivos .desktop em ~/.local/share/applications . Você já verificou?
Além disso, usar o Centro de Software para excluir aplicativos deixa os arquivos de configuração do sistema para trás. Se você quiser se livrar deles também, você pode querer usar:
sudo apt-get purge package_name
Em qualquer caso, você precisará se livrar do arquivo de configuração em sua pasta pessoal. Estes são principalmente em ~ ou em ~/.config ou em ~/.local .