Danke für eure Hilfe.

Nach einer dreistündigen Sitzung mit unserem Admin und einem anderen Experten in unserem Büro haben wir festgestellt, dass der IIS nicht mehr einwandfrei funktioniert und offensichtlich der Ursprung des Übels ist. Anscheinend ist das Ganze bei der Einführung des Zertifikats passiert.
Pech. Also müssen wir wohl für einen Systemfehler, welcher durch eine Standardprozedur verursacht wurde, bluten.
Momentan funktioniert der Sync wieder über eine Nokia - Zusatzsoftware (intellisync), die direkt auf den Exchange zugreift (übrigens was ganz tolles - synct sogar Notizen - , aber leider mit monatlichen Kosten verbunden)
Sieht momentan so aus, als müsste der IIS neu installiert werden, was gar nicht so lustig ist. Bei unserer Größe ist das zwischen einer und 10 Stunden Arbeit.
Ich melde mich nochmal, wenn das Problem tatsächlich gelöst ist.