You said that the fans are clean, but how about the heatsink over the CPU? Sounds redundant, but it needs to be asked. Also if the by design the CPU circuitry is designed to shut down the system when it gets too hot. That being said, how can you be so sure that the heat sink fan is spinning long enough?
Can you swap out the power supply? Testing another power supply will help reduce the possibility of the currently installed PSU not supplying enough power to keep the fans running at optimal speeds.