Emin olmamakla birlikte ;
Yandex mail kullanan bir müşterimde (5 yılı geçti ama ayarları yapalı)

MX kaydını doğru yaptıysanız DNS yönetiminden;

TXT değerini "v=spf1 ip4:HOST IPNİZ include:_spf.yandex.net ~all"

olarak girerek dener misiniz.

Panellerde farklı yerde olabilir, ben Direct Admin kullanıyorum. (Direct Admin DNS yönetimi kısmında)