Сообщение:
То есть это письмо уже хранится в п/я не в формате MIME.
Проверьте, переключается ли кодировка в письмах пользователя, у которого всё хорошо.
(Кстати, какие версии у Вас сервера и клиентов.)
Такое бывает, например, если БД п/я пользователя старой версии ODS (создан в 4 версии Lotus Notes и не был конвертирован).