we'll leave rooting out the cause for the moment
Just be aware that trojans get bundled in with popular downloads if downloaded from 'dubious places'
in any event > try this > find the application files as you listed in your first post. When you right click regedit and cmd > under properties are they listed as .exe application files or .com files ?? They should be .exe files as in this example below
also, have you run an adware/spyware/virus scan so far ? Even If that particular pc is not directly connected to the net, it is still vulnerable if youve installed program/apps or transferred files onto it from external sources. A friend of mine recently got a virus infected file on a usb stick which he unwittingly spread around
also, from the run prompt, can you also start the taskmanager?
let us know how it goes