You do not mention what OS you are running but that is not important for the following procedure:
Before we start, how much did you pay for your PRAM batteries? Just wondering what you considered expensive.
Did you try any Graphics cards that were PCI and not AGP? There is a possibility that the AGP slot has gone bad. Just a possibility right now.
What happens when you put the graphics card from this machine into another Mac?

Try this:

1. Shut down the machine and disconnect all peripherals other than the keyboard and mouse. Also disconnect the AC power cord
2. Open the side and remove the PRAM battery.
3. On the front of the machine, press the power button. Nothing will happen but the remaing charges held in the logic board, will be discharged.
4. Press the CUDA button ONCE only. Small button that looks like a pencil eraser. It sits in a small metal square and is near the battery holder.
5. Go for lunch for at least 20 minutes.
6. Battery back in, reconnect AC power cord. Shut door
7. Fire it up.

What happened?