Realmente mail() lo que hace es comunicarse con tu servidor SMTP (MTA) y entregarle el e-mail a enviar. Por eso te indico que lo primero que debes hacer es revisar los log's de tu servidor de correo y ver si ahí tienes algún mensaje de error o salen tus e-mails efectivamente de tu "servidor".
Por otro lado tienes classes como
PHPMailer la cual te permite enviar e-mails por SMTP directo al servidor SMTP que tu indiques .. sea el que tu ISP te ponga a tu disposición u otro servicio .. o incluso el servidor SMTP que instales en tu PC.
Si envias e-mails en las condiciones que ese mensaje que indiqué son las mismas .. de nada sirve usar mail() sólo o alguna classe más completa como PHPMailer (que de hecho en uno de sus modos de trabajo puede usar mail() de PHP también (y por ende su configuración).
Un saludo,