When everything is stuffed (virus you can't remove, corrupted registry, system restore doesn't work) your only option is to recover Windows the long way. The full guide from Microsoft is here, but below are the important points. Note that I use a BartPE CD to make steps 1 and 3 quicker - using copy and paste is easier than stuffing around with (and potentially stuffing up) the command line... commands.
1. From a non-Windows environment (ie a live CD), delete the registry hives from c:\windows\system32\config\ - system, software, sam, security and default. Copy the ones from c:\windows\repair\
2. Reboot into safe mode, ensure hidden files are visible, and replace the owner of the 'System Volume Information' folder. Copy the registry files from one of the folders within 'SVI' into a temp folder within c:\windows\system32\config\. Rename them to be the normal names (ie rename _REGISTRY_MACHINE_SECURITY to SECURITY)
3. Reboot into the live cd environment again. Replace the existing registry hives with the shiny new ones in the temp folder
4. Reboot into regular Windows - run a System Restore and you are done.
What we did and why we did it
Windows (and all of the software on your computer) knows how it is supposed to behave because of what is stored in the registry - when you install a piece of software, the installation process adds info to the registry that explains what to do, when. If the newly installed software breaks Windows (either accidentally or on purpose), we want to go back to how the system was before the installation.
This is what System Restore effectively does - it restores the registry hives to the exact state they were at the point in time on the label - killing the new program (because it doesn't know how to 'act'), but not removing any data (the folder will still be in c:\program files\).
If System Restore fails (such as a messy malware infection that won't allow SR to run at all), or if the registry is so buggered Windows won't even start, we can use the default ones that come with a fresh installation of Windows. As you might have guessed, these hives have absolutely no idea what has happened since the computer was turned on for the first time; therefore if we stopped at this point, none of our softwate would work. The final few steps get the registry back to where it was before the 'incident' - usually a couple of days will do it - so your system is back up and running.