Hi Abs,
OK, that is a bummer to have an undiagnosable problem.
Working from the 110V wall socket outward:
A power strip doesn't help much if your home is having some sort of wiring/surge/dropout issue, maybe from a large appliance kicking in and causing a drop/surge, or, maybe there is something on the neighborhood's power grid that is a problem. A UPS, interruptible power supply can help with that--I have had good results with Opti and APC:
http://www.newegg.com/Product/...1136%2CN82E16842107109
Power supply: it was replaced, but, with what brand/wattage/etc: good name brand i.e. PC Power/Cooling, Seasonic, Corsair, Enermax, etc?
CPU cooling? Do you run Speedfan to check CPU temps?
Since you swapped video cards and the symptoms didn't change, obviously it's unlikely to be the card itself.
Mobo: replaced, check; however, possible that the north bridge is overheating, even on the replaced motherboard?
memory: would expect BSOD, not reboot with mem problems.
Overclocked Venice is indeed suspect--over time, maybe the extra heat and such has made CPU deteriorate....if the new CPU fixes problem, would you mind posting a follow up report?
Thx, and good luck,
NXIL