Yeah that would be a good call, but it's definitely not a dust issue. I dust my computer about ever 2 weeks, they look brand new.
My next guess is that your thermal paste turned to thermal crust.
Dunno what your particular warranty is on that card(whether or not taking the cooler off voids i mean) but probably worth checking that out.