IIRC the pentium D's were notorious for running hot. What I would do maybe see if you can get a better cooler than your stock one (though might be hard to find one for that socket, i forget which they used.)
If anything, definitely get some freakin thermal paste on there, most work about the exact same, it costs only a few bucks too I think. Have you checked the heatsink out? like someone else suggested, clean it out good, that dust get super caked in there and can cause some major heat issues.
How well is the rest of your case ventilated as well? clean off those fans along with the cpu fan.