Hola SeNdEr2003,
PHP no es un lenguaje que tenga la capacidad directa para entregar correo, por lo que tu problema no esta en PHP, la función mail() se encarga solamente de entregar el mail a tu servidor SMTP.
Por lo que el problema radica ahi no en tu PHP.
Saludos