This may be a long shot, but when you experience this problem, have you got a printer attached to the computer and switched on?
If I try to cold boot my XP computer with my HP multi-function printer already switched on, I sometimes get all the symptoms of everything hanging at the first bios screen. It will stay like that for several minutes, before the boot process finally decides to continue, and Windows to start up normally.
There's obviously some sort of conflict in the boot-up process. I've never bothered to try and sort it out - I just make sure that my printer is not switched on when I boot up the computer. I boot up, then switch on the printer - no problems.