Para reconstruir o cache de comandos executáveis, use rehash ou hash -rf .
Certifique-se de não desanexar a opção hash_list_all (isso causa ainda menos acessos ao disco, mas torna a atualização do cache menos frequente).
Se você não quer ter que digitar um comando, você pode dizer ao zsh para não confiar em seu cache ao completar colocando a seguinte linha no seu ~/.zshrc ¹:
zstyle ":completion:*:commands" rehash 1
Há um custo de desempenho, mas é insignificante em uma configuração típica de área de trabalho hoje. (Não é se você tiver $PATH no NFS ou um sistema com falta de memória RAM).
O comando zstyle está documentado na página zshmodule man. Os valores dos estilos estão documentados nas páginas zshcompsys e zshcompwid man, ou você pode ler a origem (aqui, da função _command_names ). Se você queria alguma documentação legível ... se você encontrar alguma, me avise!
¹ requer zsh≥4.3.3, obrigado Chris Johnsen