|Just a quick suggestion, sometimes when CPU is very hot (typically P4 i believe) it will refuse to boot until it cools down.|
you may want to check your CPU heatsink/fan and check if there is a build up of dust, you may also want to change the thermal paste to something like Arctic Silver 5.
believe it or not someone recently had the same issue with an ASUS P4V800-X motherbaord with a P4 processor. After every shutdown he had to wait a while to reboot the machine, he often tried about 10 times unsuccessfully. however when it cooled down it booted.
I immediately checked the heatsink and it was clogged up with dust and mega hot to the touch.
cleaned up, replaced thermal grease.