I would replace this with a 550watt supply.
Insanity? Overkill?
Maybe, but perhaps not.
I had very similiar problem. Had random lockups in any OS> It could run for days in windows, but anything intensive like 3d games woul lock up after 15-30 minutes. Tested every single part, swapped...