100 deg C is WAY too hot! It's possible that your processor has already incurred some damage. But in the interest of being optimistic, I'd say to run memtest86 for another 2 passes to be sure it's not the memory. Are you sure the timings and speeds are being detected correctly?
Did you check your motherboard for bad/puffy capacitors? If it's not your motherboard, then your PSU is either going bad on you, or is insufficient to power your hardware. That sounds like the most likely cause to me.
Use CoreTemp to measure CPU temps, since it's one of the most accurate programs around. Don't use ATI Tool, as it's incompatible with Windows 7. Try RivaTuner instead.
I am agreeing with Jaroslav Kucera, what you've got is a faulty electric contact, almost surely in the connector. Some random vibrations after some time will throw it off; re-seating the board might fix it for some time, or even forever if you manage to get it exactly right.
What it looks like is, your case wasn't exactly designed for that board - it's out of tolerance by perhaps one or two millimeters or less. As a result, the board does not insert snugly and neatly, but needs to be forced out of true. In this kind of scenarios, you might experience freezes when the PC is warm, or when it's cold (if the thermal expansion is enough to trigger the effect), or when a heavy lorry passes by and makes the floor vibrate.
For a permanent solution, I'd look at where the board is forcing its way: there's somewhere a contrast between the GPU board and the PC assembly - for example in the slot insets at the back. Those you can perhaps file slightly to make a bit larger, and so seat better (only, be sure to catch all the metallic powder, which should never be allowed to float near the mainboard circuits). If the case allows it, you can loosen the back assembly so that it wiggles a bit, seat the GPU card, and re-tighten the back assembly.
UPDATE:
"It looks like the GPU is leaving a gap in the socket"
Yes, it looks like that. Assuming the board is not warped, and the connector is not warped either, this means that when the board is seated, the fit is not perfect - the board gets "pushed" laterally, and this affects the connector. It is an ideal scenario for a faulty, intermittent electrical contact.
Trying to "counter-warp" the connector might damage the connector and the motherboard. I can only repeat that there must be some point where the board is forced (either because the board is too long or the matched part of the case is too narrow); that's where you need to intervene.
I had a very similar problem with a Realtek network card years ago (when inserted with the motherboard and all outside of the case, everything would work; once inside, it would not even boot. But if I kept the card pushed downwards with a finger, then it would work). I ended up warping the case flange that was giving me troubles with a pair of pliers. Just a half millimeter perhaps, but it was enough (then the case would not close as easily as before, and I had to give the side panel a bit of encouragement too).
Best Answer
Since you have this problem on both OS, I'd recommend you to check all hardware step by step, especially motherboard. As for me, I would check it in following steps:
Both 2 and 3 steps preferably should be run from bootable media rather than from OS.
If nothing reveals faulty element, then just try to change components one at time (if you have them enough to test; buying just to test isn't good idea as it would likely cost as whole new PC). Also AIDA64 software has stress-test component, I was using it to find some issues and could recommend it too.
And I would add I had such a problem long ago. After long research I found faulty Ethernet network card driver. In my other case I had laptop beeping on boot about RAM fault and it was solved by replacing HDD. Keep in mind that sometimes problem is hiding in totally different component than you thinking of.
P.S. I'm sorry for a puzzle-headed answer, your question is too generic to provide exact instruction.