Evolution чудит.

Если гугл (как игрища с фейсом начались), то у меня за последнюю неделю штук 5 ошибок imap'а вылезало, в т.ч. и что-то аналогичное. К сожалению, шота не делал для сравнения.

Если не гугл, то попробуй чистый профиль (rm ~/.evolution ~/.gconf/apps/evolution). Бекап сделай на всякий случай.

Yandex для домена. Попробовал в первую очередь, не помогло. С pop все нормально. Может косяк со стороны яндекса?

Попробуй thynderbird интереса для, если и в нём такая ж беда, то в суппорт.