Well before jumping to thermal paste, is you card overclocked at all? If so try lowering the voltage or clock speed a bit. Also, have you tried cleaning the card with a can of compressed air to get the dust out?
I noticed you posted the same thing about your CPU being hot as well, so thermal compound is not the issue. I think a system cleaning/rebuild would solve the problem, sounds like the dust is just impeding airflow.
The card is stock OC and i'm not going to lower it from there. the card is pretty clean as well. I am having a few problems with other temps in my PC after installing some new case fans which were meant to be better than my previous ones, but so far all i'm experiencing is higher cpu and gfx temps
as i said it has a MSI twin frozr II cooler on it.
My cable management is very good for my case, it allows for direct airflow.
with the side panel of i may get 1 degree difference.
i also tried putting a small side table fan, about 200mm, blowing on an angle with the side pannel off but that didn't seem to make a massive difference.