Da ist erst einmal der Information Store von Interesse. Versuche den zu starten und schaue mal nach dem Fehler. Wenn ein abhängiger Dienst nicht gestartet werden kann, so ists kein großes Wunder...
Somit halte ich Protokolleinträge den IS betreffend für den Ansatz zur Fehlersuche.
Bei Problemen mit dem IS solltest du zuerst einmal mit eseutil die Datenbanken auf Konsistenz prüfen. Eine Anleitung dazu gibts hier:
http://www.msexchangefaq.de/tools/eseutil.htm