Es fácil: php no es un servidor de correos.
Por lo tanto no es responsabilidad de PHP que lleguen o no lleguen los correos que mandas con mail() porque sencillamente
php no es un servidor de correos.
Necesitas configurar correctamente tu servidor de correos local, o en el mejor de los casos usar un servidor de SMTP externo.
¿Entiendes lo que te trato de explicar?