Para acelerar as pesquisas de nomes de caminho, o shell mantém um cache interno mapeando os nomes abreviados dos comandos para o nome completo do caminho. Isso é provavelmente o que você está experimentando aqui.
Você pode emitir o seguinte comando para inspecionar o caminho atual armazenado em cache do programa:
hash -t xxx
Isso estará apontando para o executável ausente. Você pode limpar o cache de um nome específico com o seguinte comando:
hash -r xxx
Observe que esse problema afetará apenas as sessões de shell que executaram o comando no local antigo. Qualquer nova sessão de shell deve ter um cache de pesquisa claro e encontrar o comando conforme o esperado.