Посмтри sendmail.cf - там есть директива, кажется:
#O DefaultCharset=iso-8859-1
(не помню как пишется)
Раскомментируй, поставь вместо iso-8859-1 что надо и перезапусти sendmail. Совсем не уверен, что поможет, но вдруг... Это дело почтового агента писать правильный заголовок и Content-Type=..., charset