@JachyRawr: Hate to say it, but I think you'll have to take your iMac back to the Apple store again and get a replacement graphics card. Clearly that's where the problem lies.
@ Renru and TimoAbram: Glad that replacing the graphics cards worked for you.
Doing a little digging around, I've discovered that there have been plenty of problems with ATI Radeon HD graphics cards in Windows PCs as well - the very same cards that Apple has used in the majority of newer iMacs. Take a look at this discussion for example, which is eerily similar to the problems we've experienced in Lion:
http://www.tomshardware.com/forum/276896-33-radeon-5750-display-driver-stopped-r esponding
Apparently the power saving modes on the graphics cards use a very low core clock speed and memory clock speed, which leads to stability issues. On the PC side, the problems have largely been fixed by ATI driver updates and in some cases BIOS (firmware) updates. You can also use ATI's Catalyst Control Centre on a PC to tweak the card's core and memory clock speeds.
I suspect the issue at least on some iMacs is the same. The hardware itself is generally NOT faulty but replacing the graphics card with a newer card with a newer BIOS will fix the problem. What's really needed is a firmware update for affected graphics cards and better ATI drivers.
There have been no graphics firmware updates for mid-2010 iMacs but there are updates available for Late 2009 and 2011 (Mid and Late) iMacs. Links are available here: http://support.apple.com/kb/HT1599
If they apply to your machine, they might help.
Using Boot Camp and a variety of Windows tools I've extracted the BIOS from my iMac's graphics card (an ATI 5750, which is really a Radeon Mobility 5850), raised the lowest core and memory clock speed and re-flashed the card. So far everything has been working fine, but it's only been a day or so and it definitely needs more testing. Fingers crossed.