Аха. именно с ней родной и связано.
Одна из "тонкостей" с которой я сталкивался на Яху.

Все письма нужно отправлять в "нужной" кодировке.
Нужно отправлять именно в КОИ-8.
Потому что сайт яху работает именно по ней.
Если отправлять в вин-1251, то пройдет перекодировка.

Кодировку нужно прописать в шаблонах обязательно.

ЗЫ. Также определенные проблемы есть с именами вложений. Может отказываться отправлять.