Most motherboards read the temperature off the P4's internal thermal diode (rather than at the processor's base), but there's always a small chance that the reading may be off. What I would do is take out the processor cooler completely, clean off any dust that may have built up over time in it and make sure that there is good contact between the processor and cooling device (e.g. a thin layer of thermal paste over the top of the processor's heat spreader).
If you wish, you can invest in some thermal paste rather than use the pad that comes with the retail cooler.... a medium-sized tube of Arctic Silver thermal paste shouldn't run for more than $10 at most places..... just be sure to completely scrape/clean off remnants of the thermal pad first before applying it.
By the way, is your processor by any chance based on the Prescott core (you can tell since it differs from the older Northwood core by the 1 MB of level 2 cache and the "E" designation)? Those have been known to be heat demons, but still, 67C at idle is a bit high.