Quando você moveu /usr/local/bin/wine* para longe, seu shell ainda lembrava dos comandos que você executou anteriormente; depois de mover arquivos em seu caminho, você precisa executar
hash -r
para forçar o shell a redescobrir que executáveis estão disponíveis quando você tenta executá-los.
Para remover o Wine, você realmente precisa saber como ele foi instalado. No seu caso, acho que o melhor que você pode fazer é remover todos os executáveis do Wine em /usr/local/bin ( wine* , regedit , regsrv32 , msiexec ) e remover seus diretórios associados, /usr/local/lib/wine e /usr/local/share/wine (ou algo similar). Você provavelmente desejará procurar os prefixos do Wine e removê-los também; find / -type d -name drive_c -printf %p\n irá listar os itens para você.