I agree with tlarkin. You've eliminated software possibilities, which leaves a hardware problem. By far the most likely hardware problem that would show this issue is a defect in the VRAM on the video card.

The good news is that it is easy to replace the video card in your PowerMac. Just buy a new one (the Radeon 9800 is still available, so you could replace it with the same model if you wish--or go with a Radeon X800 for an upgrade) and pop it in.

Trevor