sei su un server dedicato tuo?
Controlla che non sei finito nella lista di spam

A me successe tempo fa, riuscivo ad inviare le email solo ai domini presenti sul mio server, mentre quelli famosi come libero, email, virgilio, hotmail ecc non accettavano le email spedite da un form in php, poi ho risolto eliminando il mio server dalla lista spam