Revisa los logs del servidor (apache,nginx,etc) y los de PHP.. quizás te den alguna pista. Probablemente el servidor no tiene un servidor smtp en funcionamiento correctamente o esta en la blacklist del servicio al que envías el correo.
Saludos
Saludos