Nach einigen Tests haben wir den Fehler bemerkt. Das Zertifikat war noch nicht im Zertifikatsspeicher des Users installiert, deshalb wusste Outlook nicht, mit welchem Zertifikat die Mail signiert werden soll. Ich habe fälschlicherweise angenommen, dass beim Importieren des Zertifikats in Outlook dieses auch im Zertifikatsspeicher abgelegt wird. Falls noch jemand mal auf das Problem stößt, einfach das Zertifikat in der Benutzersitzung mit den Standardeinstellungen des Assistenten installieren und Outlook neu starten, danach kann man problemlos Mails signieren und verschlüsseln.
