Have seen similar problems in the past - after a re-install it's very unlikely to be a unique-to-you software problem, so then if it looks like a hardware fault, walks like a hardware fault, and quacks like a hardware fault...
It may not happen all the time as the fault may only affect a small part or function of the video RAM and you can't easily test the entire video memory space (let alone all the functions of the GPU itself). Playing videos proves nothing as that will will only test a small part of the video system (ditto games or any single type of app).
Oh, and the Apple Hardware test is very basic: I had a bad DIMM that passed the Apple HW Test just fine, but failed when
properly tested using
memtest. Don't trust any hardware test that runs for less than "overnight"!
On: "You need to deal direct with Apple". Just mention the magic words "office of fair trading" (or equivalent outside of NSW) and they should change their tune. It's the retailer's legal responsibility to fulfil any and all statutory obligations, including "fit for purpose". Having said that, you'll have less grief calling Apple direct :-)
Rgds,
Ben