I found the following article while trying to figure out why a new SBS 2008  server install would not automatically start the Exhange information store after a reboot.  

The steps resolved the issue for anyone who has experienced this problem, Microsoft seems to have a solution to your dilemma.

http://support.microsoft.com/kb/555859

The following knowledgebase will help you to resolve Microsoft Exchange Information Store in Exchange 2007 fail to start after reboot problem
Back to the top
SYMPTOMS

After installation of Exchange 2007 Server on Windows 2003 64 Bit / Windows 2003 R2 64 Bit Domain Controller,

the Microsoft Exchange Information Store may fail to start after reboot
Back to the top
CAUSE

The "Microsoft Exchange Information Store" try to start before

"Microsoft Exchange Active Directory Topology Service" service gather

the required information to operate from the Domain Controller.

Back to the top
RESOLUTION

Note: Before editing the registry its recommended to review:

http://technet2.microsoft.com/WindowsServer/en/library/875762e7-a9fa-4ca...

1. Click on "Start Menu", "Run" and Enter "Regedt32".

2. Expand "HKEY_LOCAL_MACHINE\System\CurrentControlSet\Services\MSExchangeIS".

3. On the Right Pane, Double Click "DependOnService".

4. At the end of the Value Data, type "MSExchangeADTopology".

5. Close Registry Editor.

6. Reboot the Server.