I have an ASUS N7600 GS and I had a similar problem. Whenever I was starting to use the card with some 3D stuff, few seconds after I wag getting what looked like to be a freeze.
You know what? by increasing the voltage of the AGP bus to the maximum my motherboard (ASUS A7V8X) supports (1,9 V), the problem disappeared for a while. Probably that current is used for the on-board memory, I don't know, I am not an expert. But this did not solve the problem in the long-run. I have decided to do as you did, magicmarkus, tomorrow I will send the card to the dealer and get a new one.
As a side note, I am running openSUSE 10.2 and the problem appeared only when using the proprietary driver "nvidia". With the open source one "nv", no 3D support and consequently no problem