non è un problema di php né, a mia opinione, dello MTA: sa molto di black list.
verifica i log che dovrebbero essere in /var/log/[xxx/]mail.yyy, ove xxx/ potrebbe esserci o meno e di solito vale 'mail' e yyy è sia 'log' che 'err', magari i messaggi degli altri MX sono più espliciti (con l'indicazione della black list).
dovresti provare, dalla shell del vps, a collegarti direttamente all'MX dei domini cui tenti di spedire tramite telnet e valutare la loro risposta; potrebbe essere un problema di routing, ma propendo per le black list.
comunque a questo punto è un discorso di configurazione di server e quindi è OT per le regole di questo forum; solo un ultimo consiglio aggiungi almeno un record SPF alla zona del tuo dominio, con le black list aiuta.
ciao,
marco