-Why would the people who put a brand new GPU not get relief then, too?
As far as I know, and that might not be the whole image here, in some cases the problem might be the logic board, or even the oxidation on the contacts of the graphics card (as low-tech as it sounds), or the boot sector of the HDD might be failing, the screen itself might be failing, too. Also, some hardware installs less than well-made kernel extensions that can cause the issues with some other extensions. etc...
Most of these suspects you can eliminate through diagnostics. Unfortunately, the Apple hardware tests are not the ultimate word on this. Read this thread, people here suggested quite a few tests you can do on your own, if you want to. E.g. using your Mac as a secondary monitor, reinstalling the OS, checking whether the artifacts are present on the screenshots, too... etc.
I have been looking for a new card, too. Since the card in my late 2009 iMac is not made anymore, I could only get a used one. The price tag being very high, with my own card seemingly dead, and, hearing from the more experienced engineers that the used ones are most probably re-flowed, too... I did not want to go to the "Geniuses" because not a single time so far a "Genius" was able or skilled enough to fix the issues I had with my other Apple hardware (or software). I will spare you the rant on those guys and girls. 😉 So, I thought: what the heck, I cannot lose anything. Afterall, insides of a Mac is just another piece of electronics. Nothing magical in there. I learned about the background of the problem and did it.
My honest advice would be that if you can get a new card for an acceptable price, replaced by an authorized or experienced service and perhaps with some warranty, do that. Do not take risks.
Simplified, a cold solder joint is a soldered point which due some circumstances has developed cracks. These cracks, of couse, break the flow of the electric current and the contact is lost. Since those cracks are usually microscopic, and since there are hundreds of possible locations where they can occur, the whole electronic part (in this case the graphic card) is taken out of your computer, carefully prepared for heating and then heated to ~205C and kept at that temperature for some time. This makes the solder become liquid again and the cracks are mended. After cooling, the card is reassembled and used. This is an overly simplified description. If anyone is interested further into this, check the wikipedia, check the youtube. Give yourself a couple of days and learn. I am not writing the details here because there are much, much better sources of information on this topic already around. (of course, if you are doing this, do it on your own responsibility)