In my experience, Google flags most Yandex (and Zoho) e-mails as spam.

They probably justify it with some "you must train our network to accept your address" bullshit.