Need a soft latching power on/off that starts OFF
Have you looked at this circuit. 



If you wire it in the auto-off position, you are guaranteed to startup with no power. It uses one push button to turn on(momentary), turn off(long press) and reset(momentary). If you look throught their website you will find different circuits for different needs but i think this should do it. I have simulated it in spice and it works just fine. The 10 uF cap adjusts the time you need to press the button to shutdown the system(10uF @5v supply=3seconds). You could also use a digital pin of a microcontroller to latch it to off. Pretty neat.