This is not normal, obviously.
Here's what you need to do:
1- Get some thermal grease. Any kind will do, but Arctic Silver Ceramique is what I recommend. Make sure you get GREASE, NOT EPOXY. If it's a 2-part thing, it's an epoxy, not a grease.
2- Remove the CPU access door
3- Remove the screws that retain the heatsink in the order shown on the heatsink; do not remove the screw on the first pass. Loosen them up a bit, in the order shown, and then go back and repeat the process to remove them completely.
4- Wriggle the heatsink around gently. This is to break the "seal" between the P4 and the thermal pad, which is strong enough to rip the P4 out of the ZIF (I've done it myself several times, and I know other people that have done it).
5- Clean all of the residue from the pad off of both the CPU and the heatsink using q-tips, paper towels, cotton balls, etc. and rubbing alcohol.
6- Intel's thermal pads have a thin piece of aluminum foil in them. Make sure you remove that as well.
DO NOT, DO NOT, DO NOT use a screwdriver or something like it to scrape the pad off. Use your fingernail if necessary, but nothing harder. Otherwise, you're going to really be screwed, unless you know someone with a machine shop and a good granite surface plate.
7- take the top off the heatsink. Remove the 4 or 5 or whatever it is tiny screws, and then use a small flathead screwdriver to disengage the 4 tabs (2/side) that hold the top of the heatsink on.
8- Clean out all the crap in the heatsink using a paintbrush and canned air. DO NOT hit the fans with canned air, unless you hold them in place with your finger or a screwdriver or something. If you let the canned air spin up the fans, what's going to happen is that you'll over-rev the fans, fry the bearings, kill the fans, and have to RMA the whole damn thing to get it working again.
9- Reassemble the heatsink
10- Apply new thermal grease as per Arctic Silver's instructions (on their website @ www.arcticsilver.com
11- Put heatsink back in computer, screw it down in the order listed on the heatsink's cover. Again, just tighten them down a bit on the first pass, and then tighten them down all the way the second time around.
That should solve any overheating issues. I'll post pictures of the whole process, if you need me to, if I can get ahold of a digital camera...