Ещё какие-либо идеи есть?

Не совсем так.
Изначально, у всех всех контактов(допустим, Алиса и Боб, для наглядности) есть RSA-сертификат в локальном хранилище, он же прикреплен к их контактам в глобальном списке адресов Exchange. Далее, устаналиваем Алисе и Бобу крипто-про CSP, настраиваем в Outlook шифрование по ГОСТу, обмениваемся подписанными письмами, добавляем сертификаты в локальное хранилище на каждом ПК, в свойствах Outlook у контактов Алисы и Боба удаляем сертификаты RSA и добавляем сертификаты ГОСТ. Алиса может создавать новые сообщения, шифровать и отправлять Бобу, а Боб-нет. При попытке создать новое сообщение и зашифровать его у него появляется указанная ошибка, но вот если Алиса пришлет ему зашифрованное письмо, а Боб в Outlook нвжмет на него и выберет "ответить"-то зашифрованное сообщение Алисе уйдет. А вот новое письмо так отправить не получатеся. На компьютере Боба даже создавался локальный контакт "А." с электронным адресом Алисы (контакт, для которого точно нет RSA сертификата), и на него всё равно не уходит новое сообщение...Вот, надеюсь, максимально подробно описал ситуацию.

Вы абсолютно правы. Проблема была именно в этом. Аутлук, несмотря на то, что в свойствах контакта был явно указан только ГОСТовский сертификат, всё равно лез в AD и брал RSA-сертификат оттуда. Удалили сертификаты из AD - и все заработало.

Спасибо!