Para usar un servidor de correo que requiera autentificación .. (si es SMTP) .. podrías usar esta classe en lugar del mail() standar de PHP .. la cual, permite entre otras cosas usar servidores SMTP que requieran autentificación (incorpora ya implementado el protocolo que menciona Herminio):
PHP Mailer
http://phpmailer.sourceforge.net
Un saludo,