Дикс, и правда... Что за мода читать почту через телнет? Ты каждый раз заходишь в соответствии с RFC на свой почтовый сервак руками вбивая команды? Или достаёшь её из локальных папок сидя в командной строке?

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

Используй почтовый клиент, поддерживающий протоколы IMAP и SMTP. Я использую опенсорс решения вроде Thunderbird или Seamonkey.