I would think that you have a serious, hardware related problem and a very difficult one to find a solution through a distant diagnosis.
Intermittent/randomly but definitely occurring problems like this require a systematic monitoring/troubleshooting/substitution of components that could only be done in a professional setup.
On the face of it, it appears to be a heat related problem with some component getting quirky.
I do not repair computers

, but as a user, the first thing I shall do is to blindly replace the battery - OK follow all the procedures when replacing the battery. If it does not resolve the problem, I would disconnect all other peripherals (except the HDD) like the optical drive, Floppy drive etc, and check. Well, that is all I can do as a user. If the problem remains, the scene changes to the professional setup.
I shall ask the professional to substitute his motherboard and his hard drive with the OS with which that MB works. If everything is fine, then your motherboard is the problem area. If the problem repeats, it is your power supply.
If it is the motherboard, then the professional will substitute the RAM, and then the processor on your motherboard. If the RAM and the processor are cleared, then some component in the motherboard - most probably the video chip - is faulty. And you know the solution.
So now you know the whole process on how to get at the root of the problem.
Note: In making this troubleshooting procedure, I have assumed that your HDD is OK, since you have already said you have a new one in place. I have also ruled out the OS as a problem since you said the problem persists even with a new installation of OS.