Pero que servidor SMTP usas? .. el de tu ISP? .. uno que has instalado tu en tu PC/Servidor o usas en tu LAN? ...
Si tu actual servidor SMTP o el que pretendas usar requiere autentificación .. lo que es la función mail() de PHP por sí sólo no te servirá.
Puedes usar la classe: PHP Mailer (
http://phpmailer.sourceforge.net) que si que permite entre otras muchas mejoras a "mail()" de PHP enviar e-mail por un servidor SMTP que requiera autentificación directamente (sin pasar por "configuración" própia de PHP).
Un saludo,