This issue may not be caused by the certificate (public key) itself.
Thanks to forum ID 'Griff' for this information.

Below is one possibility:
In this case, Thunderbird was the receiving client.

• The receiving email client would not recognize that the incoming email had a digital signature attached, and therefore couldn't/wouldn't add the public key to the Certificate list.
• The message source indicated that the digital signature was indeed in there, but it did not look quite right.
• The email server in question used DSPAM for spam control, which inserts a Token into the email body showing its Dspam Verification# in the email.
• The insertion of the DSPAM Token corrupts the Digital Signature information, which is why the receiving email client couldn't/wouldn't interpret it properly.
• Reconfigured DSPAM (this is a server-side config only) to insert the DSPAM Token into the HEADER only rather than the email BODY.