Actually, unless you know something you haven't said and have extensively tested the PSU in another machine, technically it still could be the PSU. But at this stage it would be the least likely.
You said you'd tried different HDDs - does that mean you have formatted and installed the OS and correct drivers for the machine as part of your diags when trying those drives?
Does the BIOS have an option to let you check the CPU temperature? It is possible that the compound on the CPU and fan has cracked so there could still be an overheating issue.
When it shuts down does it flash up a blue screen briefly or just go off?
Does it shut off in Safe Mode?
Does it shut off when you have all extra peripherals removed (modem, printer, etc.)?