Hmmmm. I had overheating problems on my old system and Chance is right, it'll shut down abruptly instead of restarting on its own. Another way you can check this is to turn it back on, and then press DEL to enter setup. There you will be able to see the chip probe temperature in one of the menus (but don't touch anything else).
Pretty sure my power supply is 800W, but it's hard to say if that's the problem and the only way to know is to go and buy one and try it, but it could be costly if that doesn't fix your issue. Could be a bad earth on the case possibly, as one other idea?
EDIT/Flashback - I had a machine nearly ten years ago that did this - it was a a burnt out pin on one of the power plugs inside the case causing the problem. Go through your case from the power supply, just unplug and replug one by one and see if anything is discolored or smells "melty".
