Для evolution начиная с 2.30.0 (и для текущего 2.30.2-alt1) игнорируются настройки кодировки отправляемых писем при заполнении темы письма. Т.е., вне зависимости от значения поля "Правка" -> "Параметры", "Настройки редактора", "Набор символов" (KOI8-R, CP1251, ...) Subject письма кодируется в UTF-8. Тело письма передаётся при этом в той кодировке, которая указана в "Наборе символов".
Для 3.0.3-alt2 - без изменений.
Заработало в 3.6.2-alt1 .