Sounds like you either really have a card issue like a badly installed heat sink or maybe a fan is bad. I would first inspect the card and make sure it looks very clean. Look inside with a flash light. Some compressed air will clean it up good. Just hold the fans still when using the air.
Then start it up and watch the fans, make sure it or they look like they are spinning as they should. With 2 or more fans they should all spin the same.
In Wattman you can change the fan settings to kick on sooner and run full speed under high temps in Wattman. If you are using some other utility to change your fan speeds, they don't play nice with recent drivers.
If the card is not the issue it sounds like it may be an airflow issue in your case. The easy way to test this is to just open the side of the case and leave the cover off. See what that does to temps under load.
Myself I tend to run a computer till I can't get anymore out of it before upgrading. So keeping things cool helps that a lot. I have an open case all the time with a small desktop fan blowing into it when I am gaming. It really lowers the temps of everything a lot.
