Tried pressing the CUDA reset button on the motherboard? Can't remember exactly where it is but I think it may be alongside the PCI slots. I had a Beige G3 that did exactly the same thing, not even a PRAM reset did the trick, but the CUDA reset did.

I'm just throwing that out there as a suggestion. I can't tell if it was luck of the draw that the switch solved my woes, or if it truly did work intended wonders. Regardless, it got my video working again. (and several times afterward from borked Panther installs)