I've got a user who's getting this message when trying to send signed emails.  The certificates on her CAC were signed by CA-31, which is not included in Apple's SystemCACertificates keychain, so I downloaded and imported them into her login keychain, but the error persists.  There are no issues that I can see in Keychain Access… every related cert is valid.  She does NOT have the "certificate cancer" issue that was commonly associated with Entourage, unless it's manifesting itself in a way where the cert is correctly chained to DoD Root CA 2 but Outlook is trying to chain it to a fake/hidden/cached copy.  I'd asked previously about where Outlook caches certificates, as I've run into situations before where it clearly is not correctly reading certificates from the user's keychains, but nobody has ever been able to answer that.