It was purchased new. It's awful to be honest, I never had these issues before my "upgrade". I used to run the ultra wide monitor previously with the RX480 and could live with the performance. As shown in the FurMark video, the resolution on that is very low (1024x768) and it still does the stuttering issue despite it being 110-80 FPS.Was this card purchased new or used?
If the temp throttle point is set at 77C, that's pretty dang low. Usually it's around 90C. Might want to try flashing the VBIOS.
Not encouraging you to give up, but as an owner of an RX480 driving a 2560x1440 144Hz monitor, I can say that using an RX480 at 3440x1440 isn't going to give you good FPS in demanding games.