Alex433, для таких случаев есть способ отправки "SMTP Server".
Почтовики перестраховываются, и если в заголовках видят подозрительный сервер, то просто блокируют.
Это, называется борьба со спамом. "Параноидальная".
Поэтому, если функция mail() не проходит, настраиваете SMTP с данными от заведомо "белого" почтовика.
Обычно, проблема исчезает.