I had the exact same problem about 6 months ago, and believe it or not the problem was something i'd never thought it would be - Graphics card.
It was happening for about 4 months, pc restarting randomly. So I assumed it was overheating and done everything to confirm it. In the end I decided to try a different Graphics card, and to my suprise it finally stopped.
So I assume now that the Graphics card, although has it's own fan and looked to be fully working, was over heating so the pc was shutting down to avoid possible hardware damage.
It's worth a try to replace your existing one with a spare, probably best not to buy one incase it's not the solution in your case.