Random re-boots are the worst problem to fix and are usually hardware
related but trying a Live CD or even ASUS GATE ( which is a built-in
Linux Kernel in the BIOS ) will verify this as they will fall over as
well.

Fixing is a different matter and you've already started with the PSU
and CPU HSF but look at RAM and also cables ( I've known SATA cables
to go faulty just as much as IDE ones !! ) so start pulling things off
the board. Don't overlook the CPU itself - again I've seen a bad
contact with the socket cause weird problems so try taking it out and
putting back in again.

Good Luck tracking this down - it's always a long job but work at it
methodically and you should get there :-)

PS - if *everything* has been tried without a fix then you are left
with a faulty motherboard. What's the warranty situation on it ??