I went Googling and there's circumstantial evidence that
1) msgame32.exe is registered as a Service (so you may be able to put a kink in it by disabling its Service, go to Control Panel > Administrative Tools > Services)
2) an indication that your systems have Gaobot worms of some kind (there are lots of variants)
If it were me, I would start by arbitrarily locking down all unnecessary ports on my gateway router, so the systems can't connect outbound on just any old port they feel like using. Your plan of nuking the Windows installations is a good one IMHO, but keep them isolated from eachother and from the network. Do your setup and patching with the network cables
unplugged, so they don't just immediately get 0wned again before you can get your security measures in place.
Here are some resources that might help:
full-file Service Pack 2 installer so you can put that on CD for offline work.
Microsoft Baseline Security Analyzer 1.2.1 and
MBSA 2.0 both have their uses. MBSA 2.0 is better than 1.2.1 except for its inability to detect missing Office2000 patches.
...and I hope you have a current-generation antivirus product and really
sweat the details on the configuration, enable Automatic Updates for Windows, and also try to get everyone onto
Limited accounts if practical. Limited accounts are like wearing your seatbelt. The employees might freak, your software might even freak, but if you can get them to cooperate, it's a boost to your security strategy.
