Beides, zuerst hab ich den SP2 für Server 2003 installiert, dann war das Problem mit dem Outlook/Exchange Server schon da.
Dann haben nur noch den Service Pack 2 für Exchange Server installiert, in der Hoffnung, das würde das Problem beheben - brachte aber auch keinen Erfolg.
Deinstalliert hab ich noch nichts, eigentlich soll der Server 2003 Service Pack 2 schon drauf, damit auch der Windows-Search-Dienst läuft.