Help! I have a similar problem. I have a P4 3.0mhz and a Asus P4C800E-deluxe and 1 gig corsair I think. Anyway, I've used this same computer for a couple years and it's worked fine. But recently it started randomly shutting off - like I unplugged it. Then when it restarts it gives an error message saying overclocking failed. I've never overclocked it. I've read other posts saying I need to update the bios, which I did, but it still shut off after a few minutes. It seems like it shuts off quicker when it gets hotter but it may be my imagination. It's never been overclocked and it's worked fine for years. I haven't installed any new hardware or software. I've already tried changing the bios battery, then reset it and set it to default, and flashed to latest bios version. I also tried changing the power supply, but to no avail. Everything seems to be working fine... all the beeps and fans. I'm guessing it might be either the RAM, Mobo, or graphics card. Does anyone have any similar experience or know what it might be? I could use the help. It's now my kids computer and they're going crazy without it. Many thanks.

The very first thing to do is to give it a good dust out. I use a cheap 1 inch paintbrush for the job personally.
The second thing to do is to get some new thermal paste and apply it between the heatsink and CPU.