После настройки спам-фильтра в Exim отвалилась кодировка темы писем.
Вот тут (
http://danil.625.ru/2008/02/11/spam-in-subject/) советуют поменять переменную $h_subject на $rh_subject.
Что и проделываем во всем транспорте. Вуаля - проблема решена!
Спасибо Danil'у :)