Puedes intentar usar un servidor SMTP ajeno al tuyo, tal y como Gmail o Yahoo!. Puedes usar una clase de conexión SMTP como el módulo PEAR Mail o usar una clase ajena.
Yo teng una, por si te interesa:
Clase AMailer
Capaz que los servidores de correo, como no conocen el origen del correo electrónico, lo tachan de SPAM.