Today I gave in and installed fglrx. Despite considerable torture the system is
stable, so I can at least rule out some hardware problem.

Do you have any suggestions on what I can do to help fix this problem?
Considering that I have a way to reliably reproduce these GPU lockups, that I
have the kernel source to play with and that I can ssh into the system, I may
be able to gather more information. Unless the problem is likely to be in the
firmware.