The Notes client encrypts an email with the recipient's public key. A person's public key is stored on his person document. However, local contacts and recent contact also contain these keys.
The process in which the client looks for the public key is similar to the name lookup (finding the recipient when sending email) and is affected by the Recipient name lookup preference in the Location
document.
In this case, the sender likely has a local contact or recent contact entry (or Mobile directory catalog) for the recipient which has an outdated public key and that public key was selected during the look up.