Difference between "command not found" and "no such file or directory"?

That's because bash remembered your command location, store it in a hash table.

After you uninstalled node, the hash table isn't cleared, bash still thinks node is at /usr/local/bin/node, skipping the PATH lookup, and calling /usr/local/bin/node directly, using execve(). Since when node isn't there anymore, execve() returns ENOENT error, means no such file or directory, bash reported that error to you.

In bash, you can remove an entry from hash table:

hash -d node

or remove the entire hash table (works in all POSIX shell):

hash -r