Como o código PHP é distribuído para seus servidores? Do controle de versão? Copiando-o da estação de trabalho dos desenvolvedores? rsyncing do servidor mestre?
O que eu estou pensando é que alguém usando o Windows pode ter editado o arquivo PHP gerando os e-mails diretamente naquele servidor, fazendo com que os feeds de linha sejam \ r \ n (DOS) apenas \ n (Unix). Isso pode atrapalhar os cabeçalhos das mensagens de uma forma que alguns clientes ainda possam mostrar suas mensagens, mas outras ficariam confusas.