useful_faq | gmail и кодировка

Периодически мои почтовые визави жалуются на нечитабильную кодировку моих писем с gmail. Причем обычным способом (собственно сменой кодировки в броузере или в интерфейсе почтовика читающим человеком) это поправить не получается. Самое странное, что это случается не постоянно, а время от времени, у жалующихся ящики на разных серверах (в безобразии отмечены, к примеру, mail.ru и yandex.ru). В моих настройках gmail стоит "кодировка отправления по умолчанию".
В чем грабли и как их лечить?