If it will start after some time down, then it shuts down again after a bit, it is most likely overheating. You can usually set alarms in the CMOS to warn you of this. You may have a bad CPU fan or other fan. There is a utility called SpeedFan ( http://www.almico.com/speedfan.php ) that will be useful in troubleshooting heating issues. Could be as simple as applying some silicon grease between your CPU and fan. Try blowing a small house fan into your open box. If it helps you have your culprit.
The second thing I would suspect is the power supply, but overheating sure does look like the issue at hand.
To add to Owen’s answer, you might want to listen inside your computer for grinding noises coming from the fans,
and also feel the exhaust coming out. If it is uncomfortably hot, then you definitely have a cooling issue.
However, it might be an issue with the thermal compound between your CPU and HSF assembly. There are many
programs available that will tell you the temperature of components in your PC. I would recommend EVEREST Home Edtion,
which is available at http://www.majorgeeks.com/download4181.html. In EVEREST, go under Summary and click on the Sensor tab to see SMART information as well as the CPU core temperature. For a Pentium 4, normal temps depend on the core used. For example, Northwood P4 cores run much cooler the Prescott cores. If the temps are anything over 170 F while idle then you have a problem.
It also sounds like your motherboard is freaking out about the crashes which is why you get those messages when
you reboot. If you are not having a cooling issue (after checking with the above steps), then you should test the power supply and the motherboard. Also check in the C:\Windows\Minidump folder to see if your random shutdowns are actually
STOP errors. To test this go to Control Panel > System > Advanced > Startup and Recovery and uncheck the
“Automatically restart” option. This should cause you to see a blue screen if it crashes.
Finally, if none of these options work, I would suspect a hardware issue. Pick up a $20 power supply tester at your electronics store and test your power supply, If its good, I would suspect your motherboard. If its under warranty still, you can RMA it, if not then its time to go computer shopping again