It was a little cloudy about the Restart, but I heard about the Shutdown... I again didn't do much research, but I do know that there is a shutdown hibernation mode.
Problem still persists though, hmmm. I'm thinking now that, just like Windows updates. There is a storage location that is checked at some point in time which tells the PC that there was a pending action or unfinished action even before the PC was shut down. Windows 7 uses this kind of strategy to tell the system "wait, before you start any of the processes, we may need a handle on those in order to make some changes, THEN you can start up". Noticed the updates would start somewhere at the stage of the secure desktop?
Perhaps Microsoft carried this method over to this maintenance thing...? I can't see any other reason why it would still recognize that it's in Maintenance.