There are several possible resolutions to this issue, as the error 0x80004005 simply indicates that the Exchange message store failed to start. It would help if we knew the Event ID associated with this error sequence.
Microsoft has some info here:
Per one of the moderators at MSExchange.org:
” …0x80004005 usually means there is a permissions problem. Make sure you have permission inheritance turned on from the organization level all the way down to the store. ”
There is additional information (including registry hacks) here: