I had one of these servers. Its shut down time was really long (15 minutes) and after restart the information store service did not start automatically.
I found out that the problem was that this server was the only GC (global catalog) server in the affected site. It is KB829361 that gave me a clue. Adding the GC role to another DC at this site solved the problem.
Edit to answer a question:
To add a Global Catalog in your domain:
- Start Active Directory Sites and Services
- Sites - Site your Exchange server is in - Servers - DC you want to become GC -NTDS Settings
- Right-click NTDS Settings - Properties and check "Global Catalog"
Monitor the "Directory Service" event log of the server to validate that it becomes a GC. It may take a while depending on your domain size.