Sounds like the exact same problem I'm having, but I have an ASUS P8P67 Deluxe. And I've tried essentially everything you have. Memtest, multiple installs of Windows, switching the hard drive I used, switching the SATA port I used. Even tried cold booting only with the essential mouse and keyboard attached to the computer. Still no go.
Cold boot, instant BSOD. Wait on the BSOD for 20 or so seconds. Reboot. Get into Windows 7 just fine. Can play games for hours, surf web, play Bad Company 2 for rounds on end. Absolutely no problem. Just that initial cold boot phase. I contacted ASUS Tech Support 3 times and finally got what I imagine was a competent technician and we determined that I might just have a defective board. I ask him if my ram might of been the issue as it was not on the Qualified Vendor list for the motherboard, but he said he highly doubted it would of caused that kind of problem as it seems something had to "warm-up" on the motherboard before stability took place.
Sadly, the whole SATA 3.0Gb/s port issue has pushed any ability for me to get an instant replacement, so I just have to go with the general flow of the replacement program they have running.
ASUS has told me that it appears as though they are manufacturing completely new boards with the revised chip, so essentially you'll have to send in your old motherboard and they'll send a brand new one to you (rather than receiving your old board, taking out the bad chip, and soldering in the new chip). So I just have to play the waiting game for the day I have to send mine in. I'd suggest you do the same and sign up for the replacement program if you haven't already.
Or if you find the problem, let me know!
Good luck!