NF4 / ULi M1695 Reboot Issue

[Briton]

Alright, so the problem that I have is this:

I'll be able to install an operating system onto my machine (listed in signature) and use it for some time (this can vary from several hours to days) without an issue. Then what will happen is that it will just reboot and not get video at all, no matter what I do (clearing the CMOS, reseating processors, ram, video cards) and then I'll just say screw it, leave it for a while, then one day I'll try to power it on and it'll boot up fine again and work for a varying length of time. Sometimes when it reboots, it'll POST, and then just keep rebooting itself.

Now for what I've tried:

New processor (RMA'd the processor, so it's brand new)
New RAM (RMA'd all 4 sticks of the ram, so it's brand new)
New motherboard -- I switched from the NF4 Ultra-D to an Asrock 939Dual-SATA2 since I'd tried replacing the processor and RAM already
I tested all the rails on the PSU, all of which were fine.
The hard drives have been put through the manufacturer's tests and passed.

Now the only thing I can really think of is the video card (since its the only thing that hasn't changed). On both motherboards I'm getting the same problem, so it's not the motherboard, chipset, or anything like that (both have the latest BIOS).

I'm thinking I may have to try and RMA the video card (god I hope it hasn't been 3 years, I know it's right around that, though). Anyone have any experience with ATi RMA's since they've been taken over by AMD? (I know AMD is fantastic).

Any suggestions would be welcomed.

Thanks,
Briton