Bende böyle sorun yaşamıştım. Sunucuda mail.domainkey diye bir kayıt varken yandex oluşturmuyordu bu kodu.
Silerek tekrar yandexe sıfırdan ekleyince düzeldi.