'You do not have a valid certificate to encrypt to this recipient'

1. Ask the recipient to send you a digitally signed email. 2. Right-click their name on the signed message > Add to Contacts > Save. 3. New message > address from Contacts > Options > Security Settings > tick 'Encrypt message contents and attachments' > Send. 4. Or look the person up at https://dod411.gds.disa.mil, download their cert, create a contact, and attach the cert to it.