Отправка писем через mail() функцию это не нормальный способ, нормально это через SMTP, если все же надо отправлять через mail(), то необходимо убедиться что в php.ini вашего хостера, она правильно настроена, но все же еще раз настаиваю на том, что это не нормальная отправка писем, слишком велик риск попасть в СПАМ.