Verschlüsselung mit Outlook 2007 funktioniert nur in eine Richtung

Hallo an Alle.

Folgendes Problem:
Als einziger Mitarbeiter in unserer Firma mit "Hardcore-IT-Wissen" soll ich mich um die Verschlüsselung unserer Mails kümmern. Wir haben keinen eigenen Exchangeserver, sondern verwenden Microsoft Online Services, de facto laufen unsere Outlook 2007 unter Win7 aber autark.

Ich habe mir zu Testzwecken ein (für Privatleute kostenloses) E-Mail-Zertifikat bei Comodo besorgt um mit einem Kollegen, der mehr oder weniger Dauerhaft bei einem Energieversorger tätig ist, Mailverschlüsselung zu testen. Diese Firma hat eine echte PKI mit TrustCenter als Root und der eigenen Firma als SubCA.

Folgende Vorgehensweise (lehrbuchmäßig)
- ich schicke ihm eine mit meinem Zertifikat digital signierte Mail
- er empfängt diese und fügt meine Kontaktdaten samt Zertifikat und damit Public Key in sein Outlook Adressbuch ein
- er schickt mir eine mit seinem Zertifikat digital signierte Mail
- ich empfange diese und füge seine Kontaktdaten samt Zertifikat und damit Public Key in mein Outlook Adressbuch ein
Soweit so gut.
- er kann mir eine Mail schicken und diese mit meinem public key verschlüsseln und diese Mail kommt auch entsprechend bei mir an (Outlook-Mailvorschaufenster sagt, dass es die Mail nicht darstellen kann, wird die Mail geöffnet, ist natürlich alles sichtbar)
- wenn ich ihm eine mit seinem (bei mir vorhandenen) public key verschlüsselt schicken will, erhalte ich die Fehlermeldung, dass das Zertifikat nicht vorhanden ist (Blödsinn, sehe ich doch in certmgr.msc) oder abgelaufen (Blödsinn: Juni 2012) oder nicht verwendet werden kann (???) oder die Verschlüsselung nicht kompatibel sei.

Tja, und damit klinke ich mich aus. Ich habe keine Ahnung. Wenn ich mir sein Cert ansehe, sehe ich den kompletten Zertifizierungspfad von TC bis zu ihm, das Cert ist auch für "Mailsicherheit" erstellt, also für meine Augen alles i.O.
Dennoch behauptet diese Firma, dass das Problem auf meiner Seite sei.

Bitte, vielleicht kann mir jemand schnell helfen.

1000 Dank