Meu primeiro palpite pode ser o tipo de codificação para os e-mails. Eu lembro de um tempo atrás que eu tive problemas com e-mails codificados como "Rich Text". Tente mudar para HTML ou Plain Text e veja se isso ajuda em alguma coisa.
Há também uma configuração no Exchange Server que pode determinar o tipo de codificação a ser enviado. Por exemplo, desabilite emails em rich text no lado do servidor.