Yeah, ideally they aren't suppose to go over 62C, but they often ran hotter than that. The stock cooler wasn't really up to cooling it. I've seen the higher clocked models run around 80-90C. I remember the extreme edition could run some ridiculous 97C or something before being immediately damaged.
Make sure you have good case ventilation and are using good thermal paste.
wow man.....!!!!72 ?????????wow...i have same,but owerclocked cpu.its runing up to 3.25GHz.its idle at 38ºC and 49-51ºC at full throtle.but i replace my stock cooler with coolermaster set with 6 heatpipes and 10cm fan at 2500rpm.my case is totaly open near 22" crt monitor(a litle sun) and its only 51 max.and yea i used stock intel thermal paste from intel set....menn your cpu is sick :: )))) try with bether cooling system