Try a live boot CD and see if it happens with that too. I would guess it does, pointing at a hardware problem.
Your symptons look exactly like what I have experienced. I think that some of the tiny solder connections on your GPU have broken, which is a pretty common problem on laptop, X-Boxes and desktop PCs with poor case ventilation, as heat/cool action breaks the brittle solder.
What need to done (if this is the case) is a professional BGA reflow, which may not be worth it for an old graphics card. You can attempt it yourself, using a IR thermometer and heatgun (I've done this on a couple of ThinkPad laptops, once worked), and some people have even claimed done it by sticking it in the oven, or even by using a blowtorch (check YouTube).