Y si tu SMTP de tu proveedor (ISP) requiere autentificación puedes usar la classe:
PHP Mailer
http://phpmailer.sourceforge.net
Dicha classe te permite entre otras cosas enviar un e-mail por SMTP directo usando el servidor SMTP que quieras (requiera o no autentificación).
Un saludo,