Primeiro, você deve sempre desinstalar o pacote com apt-get purge packagename , se quiser removê-los completamente do seu sistema.
Não use o locate para encontrar arquivos deletados, mas não funciona assim:
locate lê um ou mais bancos de dados preparados por updatedb e grava nomes de arquivos correspondentes a pelo menos um dos PADRÕES à saída padrão, um por linha.
Por padrão, locate não verifica se os arquivos encontrados no banco de dados ainda existem.
Execute sudo updatedb e verifique novamente com o comando locate, os arquivos excluídos não devem ser listados.