I'm not sure if there are any odd circumstances about your usage but here is my procedure (although i rarely turn off)

Unplug from power
Wait 5 seconds
Quickly press-and-release power button
Select 'Switch Off' from menu
Wait at least 5 seconds before trying to turn on again
Press and hold power button until screen lights up
Wait for boot up to complete
Return to power if needed

There are probably shortcuts but most weirdness i've encountered occurred when changing the power status (plug in or unplug power in the middle of that process). Is the above process something that will not work repeatedly? Since i rarely shutdown i've found doing the above is much better than prying the battery out of my n800.