I've got an old 650MHz AMD Athlon K7 Slot A machine with this exact problem. Tried everything except the PSU, which seems a likely culprit, as there has been a few times where it will shut back off again after pushing the power button (yes, i'm pushing it long enough).
Of course it probably didn't help that the CPU was halfway out of it's slot when I got the machine, but that was the first thing I fixed. Thankfully, with it being a Slot processor, there are no pins to get bent.
I did notice an immediate change in it's behavior after putting the CPU tightly back into it's slot. Before I did that, it would take about 3 seconds of holding the power button before it would power down. After putting the CPU back in properly, all it takes is one tap of the power button to turn it off, which, from other machines, like my HP, I know how they power down with only a tap of the button, but only before the OS is loaded.