I recently purchased a computer from a friend with a Intel Core 2 Duo E8500 CPU @ 3.16GHz.
It currently sits in a fairly warm room (but cool weather is coming soon, fortunately) and I found that after playing Oblivion (a fairly powerful game) for about 1-2 hours, the core temperatures on the CPUs jumped to about 72C. About 10-20 minutes after the game, they went down to the upper 50s. Idle temp I'm finding is about mid 40s to low 50s.
Do these temperatures seem safe? I do plan to cool the room down a bit, but the computer already has some fans in it.
I would suggest taking the chip out, cleaning it properly (with alcohol if you can, but if not a simple micro-fibre cloth works well) and then reseating the CPU with some new good quality paste such as MX-2.
I recently sold an old computer that I did up for a friend.. it was using a Core2Duo and was idle at 45C. Cleaning the heatsink (removing all dust and fluff) and seating with some new (and better) paste reduced idle temps to 39C.
Remember cheap thermal compound dries up to almost a powder. Getting some quality paste makes all the difference.