Consider that you are sending an encrypted eMail to a recipient who has multiple certificates stored in Active Directory. The key question is: Which certificates are selected by Outlook 2003/2007?
When sending an encrypted eMail, Outlook actually requires two certificates. One certificate is owned by the recipient and one is owned by the sender. The recipient’s certificate is used by the sender for encrypting the eMail which is sent out. The sender’s certificate is used by the sender to encrypt the eMail that is stored in the Sent Items folder in Outlook.
For background information about digital certificates and Active Directory Attributes see the General PKI Planning Considerations on Microsoft TechNet.
Finding a valid certificate owned by the recipient
To find a valid certificate owned by the recipient, Outlook verifies if any certificates are stored in the userSMimeCertificate attribute in Active Directory. If so, Outlook examines the PKCS#7 blobs to find out if Outlook is the one that published them. In that case, there is an extra signed attribute that indicates which is the default certificate. If the certificate marked as default is found in the userSMimeCertificate attribute, it is chosen. If the default certificate is not found, the first valid certificate in the store is selected. In case the userSMimeCertificate attribute stores no certificates, Outlook queries the userCertificate attribute in Active Directory. The first non expired certificate that carries the Secure Email OID 126.96.36.199.188.8.131.52.4 in the Enhanced Key Usage and has the appropriate key usage is used. In case of message encryption, the Key Usage must be equal to Key Encipherment (20) while for message signing the Key Usage must match Digital Signature (80).
Finding a valid certificate owned by the sender
Outlook accepts the certificate that the user selected in the Security Settings unless the certificate is invalid. If the certificate is invalid, Outlook tries to find the certificate that is closest to the bad one. The selection code looks for a valid certificate from the same issuer (in case the certificate in the Security Settings just got renewed) and if one is found, it puts it into the Security Settings. If the Outlook profile contains no valid Security Settings or there are no Security Settings at all, then the Security Settings are (re)created with certificates that have the longest time before expiration and are dual purpose. Basically Outlook picks the certificate that will expire last and if there are multiple of those it picks the one that can be used for signing and encryption.
Forcing Outlook to create the Security Settings
See the following Microsoft Knowledge Base articles to automatically configure Outlook for S/MIME support: