Please also feel free to let me know if I need to post more specifics...
It's kinda sounding like you are having an overheating issue. Have you checked the temperatures of CPU, VReg, and Video Card while having the PC on for more then 20 min and running stressfull tests? As a rule of thumb, if components are just too hot to touch for more then half a second then they are usually running too hot. Although sometimes if a heatsink is off or not making a solid connection the heatsink will feel cool while the part under it is burning up.
If you don't change any settings, you just go into Back-to-BIOS mode and then exit... nothing changed in your system. This is one thing that leads me to believe you are having a thermal issue. Sitting in BIOS Setup is not very stressfull to the system and perhaps those hot components just have time to cool off, which is why they work again.
Changing the keyboard or monitor without turning off the power or unplugging will give that message screen. If you are not doing that then it is also possible that the advice to power on the monitor first is proper. Years ago it was recommended to power on the entire system simultaneously but not now. I don't know why my screen sleeps soon after resuming from hibernation, but that confuses some people. My only slow bootups occur after overnight shutdowns with onboard graphics or an 8600GT with Vista 64-bit. Win 7 with a 9600GT always starts fine. I suspect the monitor (or the connection) if not the monitor power on issue.