Mail encryption fails

My intention is to send a mail encrypted out of a Domino-Environment. I have send a mail from outside with a valid certificate to the domino-mailadress and within Notes I get the certificate (at least I see it). Then I saved the contact into my local adressbook - also there I can see the certificate.Afterwards when I want to send an encrypted mail to this address every time I get the error “Mail encryption failure: […] certificate could not be found in the directory.” The client should be configured properly - I rechecked everything several times.

I hope to get some help here - any suggestions in this matter would be gladly appreciated.

Thanks in advance,

Thomas Schmutz