Cannot Run CMD, Regedit or reged32 from Start Run

I have 3 machines on a network having this problem. If i try to run any of the above the Desktop goes blank then the icons reappear. Seems to be some sort of Virus or Spyware as it has spread to  3 machines.

 I have run superantispyware, it comes up relavtivly clean only a few adware cookies. Same problem happens in safe mode.
Ran Symantec antivirus, comes up clean. Can get into the registry using a third party registry editor but the usally suspects appear clean.
 Ran CCleaner - Nothing, reinstalled SP 3 - still same problem.
 Installed the lastest version of AVG and ran scan with that, still comes up clean.  
Super Antispyware not allowed to update, tells me the firewall is stopping it, but the firewall on the machine is disabled. We have a corporate firewall which is not blockig access to the site.

I can run Command from the Start Run menu.

Hijackthis comes up ok.

Tried to rename cmd.exe to oldcmd.exe but a new copy appears straight away. The version on the machine is the same size as the version on the xp cd.

Any ideas, when it was just one machine I was going to reinstall XP but cant now with it spreading.