I had the exact same problem as yourself on my p5k deluxe and posted in this thread a long time ago. Sometimes the system would boot but no display output. Sometimes I would get an OCing failed message even though I was running everything at stock.
Flash with the following BIOS, BIOS 0123 which was the first BIOS released for the p5k deluxe (came on the CDs with the first batch on P%K Dlx's:
http://www.sitalchauhan.pwp.blueyond...Other/0123.zip
With this BIOS flashed your system will boot up perfect every time and the problems will completely disappear.
What I did was flashed to this BIOS 0123 with all default bios settings, then set all my settings and voltages manually in the BIOS and had my ram in the black slots. Then flashed the BIOS to the latest with all bios settings manually set, and then everything worked perfect on the new bios version. I can now even overclock everything without any problems.
However, for some people no matter what, only BIOS 0123 would work and all other would have the same problems. You can either just stay on 0123 until they possible find a solution, or RMA your board. People with this exact problem have RMAed their board and their replacement's have worked perfect...
Let me know how you get on