Very weird Explorer.exe bug/virus

Hopefully I did the right thing by putting this thread in Operating systems.

Short story:
-Downloaded a virus executable
-It did some stuff, then asked to connect to internet
-I denied it access to internet
-Everything seemed fine (I've found that many viruses give up after you deny them)
-Later I restarted the computer for unrelated reasons
-Then I start up an online game, and while I'm playing it, Zonealarm suddenly minimizes it to ask me if I want to allow a program internet access.
-I click yes too fast to know what I'm doing (in the moment, I wanted to get back to my game :3 )
-This is when problems start.

Symptoms are:
-System restore not working ("Your computer failed to restore to the point.... please choose another point etc)
-Explorer.exe always exits itself. It always kills itself after running for about 3 seconds. Sometimes it loops by starting itself up and killing itself several times CRAZY: This happens even in safe mode! Repeat: This AFFECTS SAFE MODE.


Basically, I can't do anything but run programs via task manager. I also might add that I can't see any suspicious programs running -- not that it matters, since this is happening in safe mode =O

The only option I can see (and I don't much want to do it) is to insert my Windows disk and perform that "repair Windows" thing. They tell you not to do that unless it's an emergency, though, cause things can go wrong. And I don't want things to go wrong, since I don't have the patience or time to fully reconstruct my Windows installation.

Has anyone heard of this? It seems very curious to me--not virus-like at all.
Oh, and how would I go about fixing it, short of reinstalling/repairing Windows?

 

Recommend that you follow the instructions in the malware removal thread. This will either fix your problem, or at least, put it in a known state where we can troubleshoot further. Be sure to post all logs, and details of every scan. (ie, was anything found? What was it? Was it removed? Any scans you COULDN'T do?)

 

Aaahhhh -- Nothing seemed to work until I took a look inside the special removal procedures. Vundofix did the trick. I seem to have lost some system settings (Firefox's bookmarks have reverted to a state right before I got this nasty virus, my windows theme is Classic now, and other etc. settings.), but I don't think I'm infected. Thanks!