Your answer is in your question.
Put some thermal compound between the IHS and HSF before you turn your cpu into a paperweight .

There was some thermal compound on the fan; is that not enough?

Well, you said you didn't put any on. If it's the old stuff that was already on there, then no, it's not enough.
Arctic Silver 5 or MX-2 are the best to use. MX-2 is non-conductive.

Prescott's are known to run hot anyway, so the more help they get, the better.
Pretty sure they are designed to run ok even in the mid 70C's, but I wouldn't recommend 24/7 at those temps.

The thermal compound on my fan was new. I had just taken the fan out of the box. I think I'll get some. Would it survive until like next weekend?

I have used toothpaste (don't laugh) and it worked really well for a week until I got some thermal compound.
Make sure the HSF is sitting flat on the IHS. Some new heat sinks are not flat from the factory either, so if you have some way of checking it, I would do that too.

Thanks for your help. I'll be sure to get some thermal compound.

No worries

EDIT: IN THE TIME IT TOOK TO WRITE THIS 5 POSTS APPEARED. YOU SEEM TO HAVE SOLVED IT

Ah, yes the compound that comes with the fan would be enough if it's brand new. You still need to clean the CPU surface first. It generally takes a day or so to work at it's best, but 62 seems a bit hot even for strait away.

The general rule is not to go above 60; apparently the Prescotts throttle down at 65 by inserting a few idle clocks here and there, reducing performance.

I would re-seat the heatsink with some quality goop like arctic silver 5, making sure to clean off all the other stuff with iso-propyl alcohol wipes. But that's just me.

Since your temps are not disastrous, you could wait and see if a few heating/cooling cycles (using and turning off) cures the goop and reduces your temps to below 60 under load.

Late P4s are just generally very hot

I got one of the last P4s , a Cedar MIll 661, 3.6ghz stock. Overclocked it to 3.9.

It used to do 50-60 idle, and 60-70 under load ar the stock speed with the stock cooler

The P4s max temp is 65-75 . After that you risk damage..

Thats why intel scrapped the whole P4 Netburst atrchitechture at a huge cost and went back to the slower, but more efficient P3/pentium M architecture as the basis for the Core CPUs. You cant just keep increasing clock speeds.

But you should definately put new thermal paste and heatsink on. And good stuff. When i did that i got it down to 45-55 idle, and 60-65 under load