На вашем месте я бы занялся ковырянием в Ексчейндже или почтовиках отправителей писем, а не в вашем Эволюшене.
Проблема кодировки со дня на день будет окончательно снята по причине перехода Outlook 2010 (наконец-то!) на кодировку писем UTF-8. Те ваши корреспонденты, которые по какой-то причине используют вражескую Win-1251 или недоразумительную KOI-8, конечно будут создавать неразбериху, но повторяю: проблема не в вашем Evolution, а в сервере или прочих местах. Еволюшен вполне в силах разобраться с кодировками, ошибка видимо где-то в некорректной обработке писем на сервере или у отправителя.
По моему опыту, Еволюшен отлично уживается с почтовыми клиентами под Виндой при установленной по-умолчанию кодировке UTF-8. И менять ничего не нужно.