I bought a P4 3.06 about a month ago. After installing it, I found it to be one of the hottest running processors I have ever seen. With the stock cooling fan, and 3 case fans, this thing would run at about 70 celcius. I finally had to buy a Zalman cooling system just to get it down to normal.
The stock CPU fan is usually pretty weak. One of the reasons your CPU was getting hot was probably because you didnt add thermal paste between the fan and the CPU. Glad to hear you got it fixed.
I added the paste. It was just a matter of a very weak fan. I checked iot out on Newegg.com, and lots of reports about that processor showed users had overheating problems.
70C is frying territory. If you put on the paste, you probably put on too much. The paste is meant to be a small layer which fills in the miniscule gaps on the rough bottom of the heat-sink.
What temps are you recording with your Zalman unit? If my computer was reporting 70C and the HSF was not warm to the touch, I'd suspect a faulty temp censor.