Isso porque bash lembrou do local do seu comando, armazene-o em um hash
Depois que você desinstalou node , a tabela de hash não está desmarcada, bash ainda acha que node está em /usr/local/bin/node , ignorando a consulta PATH e chamando /usr/local/bin/node diretamente, usando execve() . Já que node não está mais lá, execve() retorna ENOENT error, significa que não existe esse arquivo ou diretório, bash reportou esse erro para você.
Em bash , você pode remover uma entrada da tabela de hash:
hash -d node
ou remova toda a tabela de hash ( funciona em todos os shell POSIX ):
hash -r