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
.