Что с DNS? Для работы обычно нужно хотя бы SPF-запись с IP-адресом сервера в DNS домена, а в DNS IP-адреса указать PTR-запись (имя должно совпадать с одним из имён A-записи на этот IP-адрес).
Попробуйте для отправки пользоваться не mail(), а подключить к проекту библиотеку, например. PHPMailer. Это увеличит вероятность того. что почта дойдет.
Дополнительно, кроме spf и ptr, по совету lubezniy, почитайте, что такое dkim
Многие почтовики не примут сообщение, отправленное через банальный phpmail, если ящик отправителя физически не существует (не создан на сервере), или попадет в спам.
Лучше отправлять через SMTP, создав реальный ящик отправителя