Спасибо за совет, тоже думал, но подозреваю, что проблема при отправке, причем на уровне скриптов.
Посмотрел входящее письмо - текст письма в формате "текст" хороший, а в "html" - с дефектами. Видимо ошибка где-то на уровне скриптов. Буду копать далее, дело скорее всего где нибудь в PHP-шной функции iconv.