The symptoms scream overheating to me, especially the 5-10 minutes before it will restart and the fact a replacement psu hasn't fixed it.
How are you monitoring the temperature?
IIRC some monitoring tools don't cover as much as others, so might be missing something like the GPU overheating.
I'd be tempted to try and check the temperatures of various bits if need by by touch in case something is getting hot that isn't monitored, and visually ensure that all the fans are spinning up.
As has been said it's probably also worth reseating the ram and videocard etc, it would not be the first time a part has been very slightly loose and as it's heated up it's shifted very slightly (it's not common these days due to the retention mechanisms, but can still happen, especially if retention clip is not pushed fully home, or a card isn't fully seated at one end).
I doubt it's the case given the specs, but if you are using a ps2 keyboard or mouse swap them out, I spent weeks and at least two complete rebuilds trying to fix a random crash that turned out to be a dodgy cable on an intellimouse explorer (ps2 connection rather than usb), when the mouse moved in certain ways a break in the cable lost contact and the PC froze because at the time anything that interrupted the PS2 connections caused the system to lock.
