Damn. Okay. I would try RMA’ing the card as their is a good chance it’s still under warranty. If you can’t do that, you can try doing what the guy in the video did, and reducing the memory clock speed. I don’t know if replacing the thermal pads for the memory will work, because the might not actually be bad. According to Tom’s hardware, the memory could be overheating due to how the card was designed. So, might have better luck ensuring good airflow through the case. Blow out the whole case and clean any dust filters if you haven’t done so already. Consider mounting an additional intake fan on the front of the computer, or the side panel if it supports. If you feel comfortable doing a case mod, you can add side fan to a case that doesn’t already support it.
Anyway, graphics cards often have a 3 year warranty, so there’s a good chance that your card is still covered. However, the fact that you replaced the thermal paste may cause you problems. So do not tell them that you replaced the thermal paste. If you’re lucky, they won’t even care (depends on the brand). But if they do give you ■■■■, lie, deny, and counter-accuse. You tell them that you never did anything to that card, and accuse them of trying to wiggle out of their warranty (which they are trying to do if they’re trying to not replace a card with a known defect just because someone replaced the thermal paste).