To simplify, you either have a problem with the hardware, a problem with the software, or both.
Figure out if your computer has boot from CD or boot from USB enabled, and the steps to boot from external media if it's disabled by default. A quick Google search often speeds this process along.
Use a live cd like the Ultimate Boot CD to check the RAM and hard drive for errors. Test the RAM with Memtest86+, and use your hard drive manufacturer's test suite, such as DLG for WD hard drives. This will rule out most problems with memory and hard drive issues. You could also check system temperatures if you wanted to rule out thermal issues.
Next, run a Linux live CD or boot a Linux distribution from USB. If this exhibits no problems and runs much faster than the installed system without any stability issues, it's boot and nuke time. Transfer any "can't lose" items from the hard drive to some sort of external media at this point. You'll want to scan these files for malware before you get them anywhere near a clean PC. It's preferable to scan these in some sort of live environment.
If you hadn't already tried the restore partition, you could choose to perform a "destructive restore" from here, but I don't have a lot of faith in restore partitions, as they can be infected by malware just like the normal partitions. This is where being a Linux user is nice, because you don't have to sweat about license keys and install media.
If your mind is set with staying in Windows, here are your steps:
Locate a system restore disc or a legitimate version of the operating system that you wish to install. Verify that it is a "full" version, and is not an "upgrade" version that requires a previous version of the OS present in order to install. Make sure you have the license key and input it correctly. Be prepared to call the manufacturer if the restore doesn't work right, or Microsoft if the OS install goes wrong.
Take the previously mentioned "Ultimate Boot CD" and run Darik's Boot and Nuke. It will take a while to erase the drive. Since you plan on reinstalling, you can use one of the quicker format modes. A "quick erase" or "DoD short" should do the trick.
Install the operating system from scratch on the (now blank) hard drive.
If necessary, transfer the old files that have been scanned multiple times for viruses back to the fresh operating system install. Enjoy the process of installing software and system updates.
Curse yourself for not having a more recent backup or implementing a system image backup routine. Vow to be better at it, and hope that there won't be a next time. There probably WILL be a next time.
format c:/