That really sounds like a heat issue.
I know you said you checked and re-checked but triple check that the heatsink pad is properly seated on the cpu. Make sure all the ram and other cards are properly seated.
Sometimes things run 'normal' heat up 'normally' and when they cool down they move a little, just enough to get a faulty connection somewhere.
Also check that the PSU is up to the task
