I'm currently servicing a 17 inch G4 PowerBook (A1139 model) that has hard drive replaced with an SSD. It looked good and passed all benchmarks until I tried running Quake III. The game starts, but locks up when loading map (or a demo). Same with Quake II (once I managed to get through the first map, but then locked up on loading the second level), or Smokin' Guns.

What I've done:

I've checked the machine with ASD 2.6.3 (all test done and passed).
I've checked the machine with OSX TechTool Pro 4 (it can test VRAM too - passed).
I've run the MorphOS memtest extensive - passed.
I've checked the CPU/GPU temperature for overheating - maximum noted temperature running Quake is 56 degrees Celsius.
I've run Quake III on OSX from an external FireWire harddrive - ran OK, but froze when running post-fight stats. Demo freezes the game every time.

What's wrong with it? Anybody's got a clue? Cause I'm running out of ideas. The symptoms look like GPU failure? But no trash/artifacts visible on screen...

Maybe some power delivery problem. Try with energy-saving profile. Without keyboard backlit. Disconnect or reroute the GPU fan (just make sure you can cool it down).

I've had a similar issue with my old PB 17'' motherboard. Even heating up the Radeon did not help and in the end I've ended up replacing the mobo. Too many micro cracks? Has it ever been dropped?

No, as far as know it hasn't been dropped and at least the exterior is in mint condition.

But now that it came to my mind koszer, why don't you also run gfx benchmark that may push the gpu to heat up and check if it performs the same?