Given we can almost certainly rule out driver issues, I suspect there could be some issue with the GPU.
If you have some utility to watch temps (EVGA precision type util or whatever ATI equivalent is) take a peek as you play games or run some burn tests.
Have you confirmed fan is spinning on GPU at rated specs? Have you checked there is no dust accumulation on the card itself?
It is quite possible that the card itself has simply developed some fault over time.
You have no said if graphical problems occur with other games of GPU intensive tasks, which would help point to issues with heat or the card itself.
If possible, try to test install some other GPU (perhaps you have a spare or can borrow a friends?), at least this will help rule out the card as an issue.