The last 8 people I've had to fix this problem for have all had overheating issues, and I notice you don't mention this in "Things I have tried"
Run HWInfo or HWMonitor in the background, and after a crash tab back into those programs and see the temps you have recorded.