Mi inserisco anche io su questo problema visto che ne ho avuto un analogo di recente, come potete leggere QUI ho risolto ma con qualche problema:

Se metto come destinatario un indirizzo del tipo gmail.com, l'e-mail arriva ma il messaggio viene ritenuto SPAM e questo è già un problema che con il PHP 4 non accadeva. E' risolvibile?

MA PIU' IMPORTANTE...
Se metto come destinatario un indirizzo del tipo @dominiosito.com non arriva proprio il messaggio, e non arriva a destinazione nemmeno se metto un indirizzo del dominio in cui risiede il sito. Comunque sempre con il PHP 4 andava tutto.

Mi chiedo, dove può stare il problema, nella programmazione oppure nell'hosting? Nella programmazione non ne sono sicuro visto che comunque verso gmail funziona altrimenti ditemi pure, se invece pensate che sia l'hosting, cosa dovrei chiedere di abilitare/fare? Che rimettano il 4 è difficile.

Forse se uniamo le forze possiamo risolvere entrambi.