OK. Managed to get a free fix (that is, replacement logic board - so don't know how long the 'fix' will last) under the Sales of Good Act here in the UK. This required walking in and framing the discussion before they could suggest any other alternative. You need to know the facts, know your rights, have actually tried to fix the problem yourself and basically let them know you're not going to be fobbed off at the 'Genius' bar.
Also be prepared to explain very clearly every single step you've taken to resolve the issue so that they can't suggest it's a software issue, although they WILL still say this might be the case and suggest a complete system reinstall - so make sure you're backed up if you can get into the machine and perform one.
Make sure you've done as many of these as possible :
Tried clearing PRAM/NVRAM
Tried resetting the PMU
Tried Safeboot (you'll probably just get the blue/black stripy screen)
Tried Cmd-R to reinstall
Tried Cmd-S single user mode and run /sbin/fsck -fy a couple of times to clear up any HDD/Filesystem issues
Tried Hardware Test (boot holding D)
Tried to boot off any another recovery media - DVD/USB Stick for instance
Tried to boot off any Linux LiveCD
Tried to netboot
Tried running Memtest for several passes
Tried removing and reseating RAM just to make sure
And finally the only option that seems to make any difference for a lot of people - logging in through single user mode, creating a temp directory, finding and moving all NVidia and ATI drivers to said directory and rebooting thus forcing the Mac to boot into integrated graphics mode and not use the discrete card. Beware, they will try to blame this for the problem (or suggest it may exacerbate the problem), but they cannot deny that this is not the root cause and if you've tried every other option and this is the only thing that worked it shows there's either a software driver issue (which they'll 'try to fix' by running a complete fresh OSX install), which we know isn't the case - or hardware issue, which we know IS the case.
If you carefully, and calmly (important to be calm and not get abusive or wound up at the guys in the store despite your frustration) explain every step you've attempted to remedy the situation and that you've deduced 'it must be the known issue with the defective GPU card solder joints' (this is really important, make sure you state it clearly that this is a known issue and that you've done your homework - you'll notice they don't argue this point) they will run some checks to see if they can get it to boot and when they can't they will check the serial number.
This is where things got interesting for me. The 'genius' (to be fair, he actually knew a decent amount for an Apple Store employee) mentioned in passing that he wanted to check the serial to see if this was 'one of the affected machines'. So he let slip that the problem is widespread, acknowledged internally at Apple even if not publicly and they have a range of serials that they know for definite are affected and have a policy in place for fixing them. They're probably compiling a bigger list based on machines that come in with the problem to get a bigger picture of just how widespread the problem is.
The machine was left with them for a couple of days, then they called to say the system reinstall hadn't made a difference and that, even though moving drivers around in the system may have been the cause (yeah, they were still trying to apportion blame elsewhere) they'd replace the logic board under the Sales of Goods Act. I didn't even have to bring the legal point up, so I'm guessing they know from the number of cases now turning up that the tide is turning in favour of their customers. But if they don't agree off their own back to replace it for free, you would be prudent to mention the Act and it should help them to come to the correct decision.
A week later we picked up the laptop, so we'll see how long it lasts this time. Hopefully long enough for Apple to do the right thing and issue a full replacement programme.
I hope my experience helps others (in the UK at least) to have their problems resolved. I note there's now a class action being brought in Canada and one somewhere in the US over this issue. Other EU member states should have similar rights to UK consumer laws from what I've read - so that's worth pursuing. In the meantime keep spreading the word and publicising the issue to as many people as you can, because you never know, they may have an affected machine that just hasn't shown the problem - yet!