Have you checked for bad caps? (here is an example of what to look for: http://www.badcaps.net/)

I have seen this more times than not when a capacitor goes bad you can get some really strange issues...

What about overheating? Does this happen if the PC sits turned off for a while then you power it on? Or does it not matter the environment prior? Could be a bad cooling fan/setup. What about thermal paste on the processor?