В заголовках и теле писем должны использоваться семибитные символы, поэтому UTF8 может не проходить - с отрезанным старшим битом вы видите то, что видите.
Решений может быть несколько.
Первое - использовать семь бит в символах (т.е. перейти на английский

)
Второе - обернуть текст в MIME (это самый правильный вариант)
Третье - Послать заголовок "Content-Type: text/plain; charset=utf-8"
Четвертое - использовать (если поддерживает) опцию sendmail -o message-charset=utf-8
(вот тут можно чуть почитать:
http://welinux.ru/post/6462/ или еще погуглить).