It sounds like bad video RAM, possibly caused by overheating or a weak PSU. If you can get into Windows, try changing the screen resolution in Control Panel > Display. If the number of vertical lines increases, it's your VRAM.
Check your system temperatures and PSU voltages with
SpeedFan. Try running with the case open and a desk fan blowing towards the card. If you don't see any improvement after reducing the case temperatures, then it could be time for a new graphics card.