По каким признакам программа должна угадать какая в письме кодировка?

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

Точно-точно? Можно ссылку на пункт RFC 2047 по которому именно ваша кодировка обозначена как единственно правильная и которую ВСЕ почтовые клиенты должны понимать БЕЗ служебного заголовка
Content-Type: ....; charset=....
? Что, слабо там такое найти будет для кодировок, отличных от ASCII?

Тогда найти того, кто его ТАК настроил, указать ему на его ошибку и ждать исправления оной. Если нет - перестать пользоваться услугами этого сервера.

Правда? Ситуацию, что сервер отправляет в кодировке, которая по умолчанию и включена в KMail для писем без указания кодировки, вы естественно не рассматриваете в принципе? Ну да, ну да

А это здесь вообще при чем??? Какое отношение web-интерфейс имеет к почтовому клиенту? С другой стороны - если у вас с web-доступом нет проблем, ну так и пользуйтесь им. Кто ж вам запрещает? К чему эти придирки к Thunderbird'у что он не смог угадать кодировку ваших писем, которую вы сами пожидили указать? Собственно он и не должен был, никто вам такого не обещал...

Наверное и коню понятно, что никакую программу никакими настройками нельзя заставить УГАДЫВАТЬ неизвестную кодировку со 100% результатом. Но вы тем не менее задаете такой вопрос... Я же вам объяснил, как должна решаться проблема правильно - не нужно никого настраивать на УГАДЫВАНИЕ, нужно просто правильно составлять отправляемые письма и тогда ЛЮБАЯ программа, написанная в соответствии с правилами чтения писем будет их правильно отображать.