Es probable que tu servidor requiera autenticación (en el outlook tienes que marcar la opción "Mi servidor requiere autenticación"???) y por ahora el comando mail no permite eso. Si ese es el problema puedes utilizar la clase phpmailer que si lo permite
http://phpmailer.sourceforge.net/