Windows – Computer shutting down randomly – NOT overheating

Desktop PC running windows 7, hasn't been formatted in about 3 years.

I recently installed & run skyrim for about 1 week with no problems (up to that point I hadn't run any recent graphics-heavy games). Then, the pc started shutting down on its own (no hangs-no blue screens) while playing. I lowered the graphics settings and it seemed to go better.

About a week after that, yesterday, the PC started shutting down on its own WITHOUT running Skyrim or any other graphics-heavy applications.

I checked the system temperatures and CPU temp was very high. I opened the case and there was a lot of dust, so I cleaned it carefully. Afterwards, CPU temperature was way lower (about 55 C).

However, after that, the computer STILL shuts down, now very very frequently (after about 3 mins after boot). It always happens in windows, although I don't have any other OS installed to test. I did try to leave it on BIOS for about 15 mins, during which time it did NOT shut down, but that might have been pure chance.

I have been checking all temperatures when booting up, and none of them are high just before the computer shuts down. No other changes have been made to the hardware/software recently, only running Skyrim, that's why I mentioned it. Once again, these new shut-downs have nothing to do with the game and happen randomly and frequently.

Also, sometimes, after these irregular shut-downs, pressing the button to switch on the pc doesn't work properly (it sounds like it's trying to switch on but fails).

Any idea on what can be wrong?

edit : Temperatures seem to be fine now, windows are genuine, there's no visible damage to motherboard or other hardware.

According to comments, I'll try booting a Linux live CD (Good idea!) and a different PSU for now, thanks.

edit2 : Changing the PSU seems to be working. System has been running for a few hours now with no shut downs.

edit3: I can now confirm that the culprit was a semi-functional PSU. Case closed