72C

thats hot. Whats your voltage sitting at? Even if you don't adjust the voltage some motherboards will increase it if you increase the FSB. I would check what your voltage is sitting at and go one lower. I'd re-apply the thermal paste too. Check out the Arctic Freezer Pro 7, cheap and cool.
When I overclocked my E6600 it never got that hot. I think the most I saw was 52C at load with a good cooler..