i had the same issue this past week when I got my 9800. i used stock cooling, but the heatsink / fan had come loose and the thermal grease wasnt so great. I redid everything and that fixed SOME of the problem.
what i might suggest to you, which is what lead me to finally fixing my problem is try installing older drivers, such as the catalyst 4.8s (available on ati's website) and also try the omega drivers (google it).
you may just be having a driver issue. I installed the catalyst 4.8s and that improved my problem some.
if your previous video card was NOT an ATI card, you also may want to use a driver cleanen while in safemode to remove your old drivers, then put the ATI drivers back on.
I ended up formatting (very tedious) but I am glad I did, everything works great now.
good luck