1. Install and Run Ccleaner (
www.piriform.com/)
a) on the Cleaner Tab, check everything except Wipe Free Space, then Run Cleaner
b) Click the Tools Tab and uninstall any software you no longer use
c) Click on the Registry Tab, check mark everything(or do them one at a time so the list isn't too huge)>Scan for Issues, then Fix Selected Issues.
d) On the Tools Tab, click on Startup, then disable any startup programs you don't think you need. Don't delete them, just in case.
2. Goto My Computer, Right Click one of your drives then Properties, then click the Disk Cleanup button
3. Uninstall and Reinstall your video drivers(might even do 1c again inbetween the uninstall and reinstall)
4. If you have a sound card, consider uninstalling and reinstalling those drivers.
5. Defrag the drive. You can use the Defrag program that came with Windows, or download one from (
www.piriform.com/) called Defraggler which works great for me.
You said your memory was rock solid, but if it was not then I would consider re-seating. Same for the video card.
If you have an air compressor, I would consider blowing out the inside of the case to remove dust. You can use canned air, but the hazard there is sometimes it comes out as a liquid.
I have experienced bad power supplies before where a computer will reboot unexpectedly. Swapping it with a spare and seeing if there is a difference can determine that. You could do what Chris suggested and use a volt meter to check if the power is within specs, assuming you had a volt meter, knew the specs for your supply and had the experience to do it.
I have had a video card go bad as a result of a capacitor that popped, as Chris suggested. Replacing the video card solved the issue. Replacing the capacitor would require finding one of the same type, getting a solder gun, and having a really delicate hand. Prolonged heat can ruin other components near the points you will need to unsolder and resolder.