Yeah, they definitely not consistent with simple overheating (dust accumulated in the vents), because that would also present itself in safe mode under load. No freeze in safe mode *at all*, is that right?
Random crashes could also indicate memory failure. If you have two memory modules, you can get out one (3 = 2 + 1?) and see if the problem persists. But that's not even necessary if they pass the memtest86+ test. It's available for download as bootable cd/usb at http://www.memtest.org.