In fact, cmd.exe shouldn't even be there under normal circumstances, so if
it is there then the problem is what I suspected. Something (virus/malware
typically) hijacked cmd.exe. That something is now gone but the hijack is
still in place and needs to be removed.

Windows would never otherwise report "cannot file <full pathname to
executable>" when you just gave it a filename (no path), and Vista certainly
would just start searching.

The hijack is through a value named Debugger whose data (an executable
filename) is run instead of the original file (cmd.exe in this case), with
the original file passed as a parameter to the debugger.

You should just delete the cmd.exe registry key (the folder icon on the left
within regedit, that you highlighted before).