Public Key Errors

Hi there, I hope somebody is able to assist with this small issue I am having.We recently underwent a certifier key rollover and were issued with a new certifier ID. I have re-certified all servers, certifiers and users. All went well, however some users are still receiving this ocassional message when attempting to open older email (those emails received before the certifications took place: The subject’s public key found in the certificate does not match the one stored in our ID file for that entity.

The user is still able to read the email, but essentially it is just a pain for the user to be constantly alerted.

We have a policy in place which automatically signs all sent email so I am thinking perhaps the above error is the result of that? I have also verified that the recipient of the email does not have the sender of the emails in question added into their personal address book (containing the old certified public keys)

I would really appreciate if anyone has any ideas. Thanks in advanced.