It sounds like there is a mismatch between the public key listed in the Directory for this person and the public key stored in his ID. I would copy his public key from his ID (it?s a button on ID properties) and paste it into his person record.
Dig Deeper on Domino Resources - Part 5
Related Q&A from Michael Lazar
Learn how to easily keep track of the numbers of incoming and outgoing Lotus Notes email messages to and from your Domino server each day. Continue Reading
Discover what steps you can take if your Lotus Domino server runs out of disk space and you have issues sending and receiving Lotus Notes email ... Continue Reading