Есть CentOS 3.6. Отправляю письмо с помощью mail или с помощью другой программы, то получаю, что тело письма приходит нормально (UTF-8, русский), в заголовке часть букв закосячена. Например, "Русский язык" придет как "Р...кий .з.к".

Думали сначала, что косячит программа которая отправляет письма, но дошли до уровня почтовика. Посоветовали вместо sendmail попробовать postfix (на другой машине с postfix и suse) все работает нормально. Но после смены на postfix проблема осталась.

p.s. Предлагать заменить CentOS 3.6 на что-то другое не надо (ибо суровые требования железа и софта). Разве что можно попробовать обновить до 3.9 (если действительно решит проблему с буквами).