Отправляйте письма средствами Яндекса ) Через
SMTP.
Используйте
https://github.com/PHPMailer/PHPMailer
Раз у вас уже подключена Яндекс Почта для домена, создайте какую-нибудь почту аля reply@вашдомен.ру. И через него по SMTP отправляйте письма. И в параметре
From можете, что угодно писать и все почтовые сервисы будут нормально его отображать, т.к. почта приходит с проверенного сервера. От Яндекса.
