Otro detalle ...
Si usas tu proveedor de internet (ISP) para usar su servidor SMTP e indicarlo en tu php.ini .. ese servidor SMTP tiene que NO requerir autentificación para usarlo (contraseña) .. mail() de PHP no puede autenticar. En tal caso tendrías que usar classes para envio de e-mail por SMTP directo tipo: PHP Mailer (
http://phpmailer.sourceforge.net)
Un saludo,