Жаловались на mail.ru тоже. Яндекс - не проверял.
Есть шанс, если написать письмо в gmail? А если делать смену dns и mail-сервера на Яндексовские, есть шанс, что поможет?
Или вот еще - завтра попробую заменить mail-сервер хостера на google (как многие здесь описывают).. А вдруг?
В любом случае спасибо за поддержку!