Пробовал подключать клиент по протоколам IMAP и POP3 - не помогло. :(
ИМХО дело в самом клиенте.

Кстати, какую версию CSP 4.0 пробовали?

Аналогично. Никаких закономерностей в самих сообщениях мне выявить не удалось.

Частично проблема похожа на описанную тут (в части заполнения файла нулями)

Проблема скорее всего где-то в интеграции криптопро-оутлук.

Судя по сообщениям на answers.microsoft.com оутлук могут смущать пробелы в конце BASE64 секции.
" I can extract it from the source, and decode it OK outside Outlook. It is Outlook that wrongly decodes it as all zero bytes. "

" The example emails we used to duplicate the problem contained spaces right after the Base64 content ended in the MIME encoded file."

Если криптопро отдает результат в BASE64 то возможно проблема где-то здесь.

Тогда у меня идей нет. Все сбойные письма нормально открываются в CryptoBird.
Изучение писем сохранных из очереди на гейтвее (на которые гарантированно не повлияли антивирусы/антиспам или другие действия наших почтовых серверов) тоже ничего не дало. Там вполне обычный S/MIME формат.

Еще возможный нюанс - само тело письма пустое. Т.е. совсем пустое. Возможно это может как-нибудь влиять. Но оно пустое во всех письмах включая те что нормально открываются.

Связывался с поддержкой АТС - их ответ "у нас есть регламентированный АРМ и проблемами другого ПО мы не занимаемся". В принципе их позиция понятна, но для наших целей АРМ неудобен. Пока остановились на Outlook и CryptoBird который берет почту по IMAP с того же Exchange аккаунта. Пользователь пользуется оутлуком,а в случае проблем открывает письмо в CryptoBird. Не совсем удобно, но работает.