You may think you uninstalled it but check the registry. Sometimes things don't get completely deleted, even after cleaning out the cache.

With this being a production machine, you really should think about purchasing software like ImageCast or Ghost. Get a good, solid build on a machine and get an image of it. Keep it on file and when you have something like this happen, it will only take 20-30 minutes to get that machine back up to where it was before it got hosed.....At least that's what my company does.

Also, go to Google Groups and do a search to see if anyone else has had the same problem. Find out what they did to resolve it.

Good luck in finding your solution.