Problem mit digitaler Signatur

Ich habe ein Problem mit digitaler Signatur aus Outlook.
Sende ich vom einem GMX user über Outlook Express eine Email Signiert an mein Outlook in der Firma, so wird in der Mail angezeigt, dass das Zertifikat nicht vertrauenswürdig ist, und die Email verfälscht worden sein könnte. Und das obwohl das Zertifikat von Verisign ist.
Das Firmenzertifikat wird ohne solche Fehlermeldungen im Outlook Express des GMX users erkannt.
Schicke ich vom Outlook Express User eine Signierte UND Verschlüsselte Mail, so wird im Firmenaccount im Outlook alles als OK eingestuft.
Hat jemand Lösungsvorschläge? Ich kann dem Zertifikat auch vertrauen, nützt aber leider nix.