Использовать реальный почтовый адрес на реальном почтовом сервере. Письма отправлять через SMTP с помощью SwiftMailer, например. Можно использовать Яндекс.Почту для домена.
Пробовали обратиться в поддержку хостинга, на котором хостится условный site.ru с этим вопросом? Если такой возможности нет (или нет желания), то советую использовать PHPMailer с отправкой писем через акк. бесплатного почтового сервера по SMTP (gmail, например).
Чтобы gmail гарантировано показывал отправлено через site.ru, нужно site.ru перенести на отдельный IP-адрес. Сейчас гугл показывает первый попавшийся домен по вашему ip.