Random computer crashes

Around a month ago I got fed up with the lousy state of the ATI drivers for linux, and went out as bought a used nVidia GeForce 7800 GTX. I then upgraded my kernel and all was fine and dandy... for a while.

After around a day both my monitors suddenly went blank for around 3 seconds before the computer suddenly rebooted. It has happened at random intervals ever since, and in all but one of the cases any music I've been listening to has disappeared too, and in the one case it didn't the last 0.1 seconds or thereabouts kept repeating until it rebooted.

/var/log/messages and the Xorg logs are both blank, I've since downgraded both the kernel and the nvidia-drivers with two different compilers, didn't help, memtest86 is clean, and a stress-test revealed nothing on the PSU whose specs are already more than adequate.

Is there anything left to try before assuming the card is flawed?

Why assume? You could just take out the card and check if your computer runs stable without it. memtest showing no error is no guarantee that the RAM is fine but the way you describe it, it doesn't look like faulty RAM to me anyways. It might be a heat issue but you've probably already checked for that.

If you still have that ATI card, why not give the open source drivers a try while you're at it. The opengl performance sucks ass, but if you aren't into games too much, it's a good alternative.