Here are some suggestions:
1) as a fact-finding step, put your case out in the open, take the side cover off, and aim a house fan in the side. Now you have lots of cooling. Give the system a heavy workout and see if the improved cooling helped fix the problem.
2) If it did, then make sure your case is in an open area where it can get plenty of air (not in a cupboard or something), and improve your case airflow. Exhaust is your friend. If your case really doesn't allow for much exhaust flow, due to very restrictive grillework over the rear exhaust fan or poor intake vents, then kick that case to the side and get a well-ventilated case. Newegg has the SLK3700AMB on sale for $64 shipped if you're in the US, which comes with a 120mm exhaust fan and a dual-fan PSU.
3) With proper case airflow, the stock pad on the Intel heatsink should get the job done, it just needs enough cool air to work with. So maybe hold off on that until you've fixed the case-airflow issue.
4) Your motherboard may be the one doing the shutdown, and 60C is premature since the P4's thermal throttling begins only at 67C (IIRC). Go into the BIOS and see if you can raise that a little.