I blew all of the dust out of it a few months ago
Months ago? Note that everyone should be inspecting the interiors of their computer cases
monthly for heat trapping dust build up, and cleaning as necessary - which could be monthly as well - depending on the operating environment, foot traffic, and the number of dander shedding mammals living in the house.
Thermal paste does not go bad and never needs to be replaced UNLESS the cured bond between the processor and the heatsink has been broken due to heatsink movement or removal. So if the cured thermal paste bond has been disturbed, then you do need to remove the old, clean the surfaces thoroughly and apply a new and proper layer of
TIM.
And if the fan is gone, that should be obvious by either slow, or no movement. But as you noted, 60°C for a graphics card should not be a problem and indicates to me there is decent cooling going on. Are your CPU and system temps good?
Before spending and possibly wasting money on a new cooler, I recommend removing the side panel and blasting a desk fan in there then see if the artifacts still appear. If they do, then you likely have a driver or failing card issue. This assumes your PSU is still pumping out good, clean, stable and enough horsepower.
Oh, and if you are overclocking, don't! At least not until this is resolved.