I registered on this forum to reply to this thread which a google search lead me to.
I was in an easier position to troubleshoot than the OP because my P8P67 Pro was completely fine with booting into the BIOS every time without fail until I upgraded two components simultaneously... I upgraded my hard drive to an SSD and my old (temp) VGA video card to a new Radeon HD5550 which I connected to my nearly brand new Pioneer VSX-32 receiver via HDMI, which is connected to my ~4 year old Sharp Aquos 37" 1080i TV.
Since only those two things change I knew it was something to do with the hard drive or video card unless something just randomly went wrong with the motherboard at the same time (doubtful). But to prevent unnecessary troubleshooting I googled my symptoms (which were identical to what the original post describes), and found this thread which thankfully saved me some time after I read the final replies.
Thankfully my Radeon HD5550 has a VGA output on it so all I did was connect that directly to my TV since my receiver doesn't have a VGA input. For good measure I disconnected the HDMI cable from the video card just in case, even though I had already turned the receiver off.
Oddly when I turned the computer back on, I got the ASUS loader screen where it tells you to hit delete to enter the EFI setup screen. But no matter how much I hit delete or waited, it just stuck there. Restarting didn't help any. Out of impatience I just reset the BIOS via the CLRTC jumper, and after that it started working fine. I went ahead and updated to the latest non-beta BIOS (1502) and then switched back to HDMI via my receiver.
I confirmed that it will still not boot into the BIOS when connected via HDMI. But at least now I am on the latest BIOS revision (which is what I wanted to begin with during this whole ordeal) and also know what I have to do if I ever want to get back into the BIOS.
For what it's worth, my computer technically is only talking to my receiver and doesn't know or care what sort of TV I have. My video card knows that it's connected to a Pioneer Elite VSX-32 which is a very new receiver design (HDMI 1.4a). So that sort of rules out the 'very old TV' theory, I would think?
OP - did you inform Asus of what you found so they won't have other users sending in their motherboards for replacement?
It's getting late tonight but in the future I might play around with my receiver's video input settings so that instead of auto-negotiating its display resolution with the source (PC), it will request a specific input resolution.. maybe something very basic like 480i?
Bah... HDMI is really such a headache all around though. It's amazing as long as it has been around that it still causes all sorts of handshaking issues between devices and now we've got this head-scratcher.
I still haven't gotten overclocking completely sorted out either so I'm going to be using this VGA cable for a while until then.
Oh, lastly, I'm still using one of the 'defective' (not rev 3) boards. I didn't realize they had released the fixed model. I never got the followup email from Newegg.
And to think I'm doing all of this build-up after hours to build up a lab machine to simulate some virtual environments and disaster recovery scenarios for my work. I haven't even gotten to the point where I've been able to start on my lab experiments because I've been so distracted by all the other issues along the way. There sure is something to be said for just buying a Dell or whatever other proven solution you prefer. LOL