O motivo pelo qual você não consegue encontrar o arquivo .deb no diretório /var/cache/apt/archives/ é porque não está mais lá.
O comando locate localiza porque o locate não examina o conteúdo real do diretório, mas funciona a partir de um cache.
De man locate :
locate lê um ou mais bancos de dados preparados pelo updatedb (8) e grava nomes de arquivos correspondentes a pelo menos um dos PATTERNs à saída padrão, um por linha.
Por padrão, locate não verifica se os arquivos encontrados no banco de dados ainda existem (mas exige a existência de todos os diretórios-pai se o banco de dados foi criado com --require-visibility no). O locate nunca pode relatar arquivos criados após a atualização mais recente da base de dados relevante.
Para atualizar o cache do banco de dados, execute este comando:
sudo updatedb
updatedb cria ou atualiza um banco de dados usado pelo locate (1). Se o banco de dados já existir, seus dados serão reutilizados para evitar a releitura de diretórios que não foram alterados.
Isso deve classificar o comando locate ao localizar arquivos que não existem mais.
EDITAR
Para os arquivos /var/cache/apt/archives/ não existentes, talvez você execute um comando clean após executar o comando sudo apt-get dist upgrade .
Qualquer um desses comandos limpará automaticamente o diretório /var/cache/apt/archives/ .
sudo apt-get clean
sudo apt-get autoclean
Fonte: Limpando var / cache / apt