I have 2 XFX 4870s in crossfire and using 11.11. I too at some point started having artifacts and quickly found out my card were overheating in games because the automatic fan control didn't seem to kick in fast enough.
I turned on ATI overdrive in the drivers and put the fan control at 35% for both, but recently I've had to bring it up to 40% 'cause the games are so friggin demanding.
Yeah, it's loud as hell, but in my basement when the house heating system kicks in, I don't hear them as much... just have to crack up the volume a bit.
I'd definitely install the latest drivers, enable AMD overdrive in CCC but don't change any settings yet, leave GPU & memory settings @ stock and run a game and watch the temps, if they shoot up fast past 85-90C, enable manual fan control and force it to 35-40%. That's if you have dual monitors, 'cause as soon as you alt-tab, temps drop down quick and might skew it all.
For single monitor, download HWMonitor from CPUID, it will record the max temp in the background, as soon as you see artifacts alt-tab to HWMonitor and see what the max was, if it's low (like under 75C), then you're having other issues; video on its last breath or not getting enough power from the PSU.