I have had similar behavior on my machine at random times, and I think it goes back to a confused loop in BIOS. First I'll describe my situation, then talk about what you could try.
On occasion my machine has failed to start up when I push the front panel button. But if I unplug the power cord OR just turn off the power switch on the back of the PSU and leave it without power for at least a minute (I assume in that time the PSU's internal capacitors are discharging to nothing), then restore power and push the front panel button again, it works just fine. The problem does not repeat immediately (unlike yours). My hypothesis is that, for reasons unknown, the BIOS somehow gets a little confused during a shut-down. When the computer is "Off" it is not completely off. A small loop in the BIOS is running checking for the power button push to initiate a re-start of the whole system. But I think sometimes that little monitoring loop gets stuck and fails to see and respond to the front button push. A full cold reset resolves that confusion.
Now, to your case. It is very similar to mine, except that yours happens on virtually every shut-down. I suggest a BIOS reset which takes several steps. BUT the very first thing is to record what you have. The Reset procedure will put all-good settings into your BIOS, but will lose any special custom settings you have made before, so you'll need to restore them manually. So, get pencil and paper and go thorough your entire BIOS Setup screens, writing down all the places where you have made any custom settings and the values there. Things like which drive ports are Enabled or Disabled, what SATA Port Mode settings you have (IDE Emulation, AHCI, or RAID) what Boot Priority Sequence you have, whether you changed any CPU timing or voltage settings, any custom RAM settings like voltages or timing parameters, how the audio port output is set up, what type of video output you have... all that stuff. Once you have a record of all of this you can start the Reset. Oh, just before you do: did any of those custom settings look odd to you? Maybe something you never changed, but it seems like a strange setting that might be linked to your problem? Make a note of that in case you want to try changing it later.
Before going further, consider the possibility that the BIOS battery has gone dead and needs replacement. You could just go buy a new one and do the replacement. OR, when you get the old one removed, you could run to the store and have them check it before spending money - you might NOT have a dead one there.
OK, now we do the reset, in these steps:
1. Disconnect all power to the machine. Open up and remove the BIOS battery - looks like a quarter - from its plastic holder on the mobo. (See note above about possible replacement.)
2. Find the BIOS Reset pin set - three pins with a jumper on the first two. Move the jumper to the middle and last and leave there for about 10 seconds. Return the jumper to its original location. Now replace the BIOS battery in its holder.
3. Close up the case, reconnect power. Boot up but go immediately into BIOS Setup. Look on the last couple of tabs for the place where you can load up pre-defined sets of BIOS parameters. Load either the Factory Default set or the Optional Default set. Save and Exit from this to save the settings. This procedure ensures that the BIOS is reset AND has all good parameters to start from.
4. Now reboot into BIOS Setup again and go back through all the screens. From your notes, re-set any of the custom settings you needed so that your machine is back to "normal".
This MAY solve your problem IF the cause simply was some odd BIOS setting. BUT if the problem persists you'll have to look elsewhere.
By the way, I said my computer had similar problems but rarely and randomly, not repeated. More recently and with a different set of symptoms that got progressively worse over the space of a couple of weeks, I confirmed that the PSU had failed and replaced it. I have no idea whether that eventually-clear problem was related to the earlier random failures to boot properly.