Для того чтобы написать кому-нибудь зашифрованное письмо, необходимо заранее получить и установить сертификат получателя. Если сертификат получен по почте, нажмите значок, на котром изображена галочка в зеленом круге и ручка с надписью в форме S, и выберите пункт "Импортировать сертификат". Далее следуйте вопросам мастера.

Рекомендация: Включите опции "Помнить связь e-mail адресов с сертификатами для подписи" и "Помнить связь e-mail адресов с сертификатами для шифрования." Эти параметры доступны через пункт меню "Свойства" - > "Параметры S/MIME".

Настраивали согласно документации: http://www.cryptopro.ru/...mentation/pdf/TheBat.pdf ? Выбирали реализацию microsoft crypto api? Если всё так, то скажите: при просмотре сертификата на вкладке "состав" есть ли поле "точка распространения списка отзыва"? если есть, то доступен ли файл CRL по ссылке, находящейся в этом поле и действительно ли в CRL отсутствует Ваш сертификат.