How hot is too hot? I have my E8400 with the stock HSF running at 3.6 ghz (9x400). Coretemp with Prime95 Blend test (1800 Ram specified) is hovering around 58-61C. It hasn't failed in an hour so far.
Those temps are a little on the high side (especially considering it's a 45nm CPU) but you're not in danger of damage. Most motherboards will start "beeping" at you at 75C. Critical is 85C. An aftermarket cooler would definitely improve things for you.
Would I be better off just turning it back down to 3ghz? It's sitting at 60C steady on both cores according to Coretemp but it seems solid after an hour. I'm trying out the one that says "maximum heat, not much ram tested" setting and it seems stable after a run through. I mainly play games so I'm not sure how much the OC from 3 to 3.6 is going to affect things.
Coretemp is based on a Tj max of 105c whereas Realtemp sets it as 95c. Thats why the difference. As far as I know there has never been any official Intel spec that tells what the 'real' Tj max is. Intel only use it fror throttling at the higher temps (which your not even getting close to). Even if its the lower of the 2, your still 35c away from max. Intel only states that your CPU case temp (Tcase) is less than 72c - keep an eye on this temp as well. Yes, a better HSF will help but I personally think your safe for a while with a max of 60ish at 3.6GHz while you save up and buy one.
You are doing a lot better than I did with the stock HSF, I was case 57c, core 65c load only at 3GHz. I quickly got a TRUE to throw on and now the temps are case 48c, core 59c load at 3.8GHz - huge difference (and I didn't lap anything).
Sorry, I forgot to say watch you Vcore settings as well. If your putting too much voltage to your CPU, it will generate more (unnecessary) heat. Try to get the lowest Vcore setting that is stable for your CPU and you should see temp drop a bit.