Este mundo es un pañuelo sin duda 
Efectivamente he tenido ese mismo problema y mira por donde es el mismo servidor que el de mis clientes. Lo postee aquí:
http://www.forosdelweb.com/f18/antes-llegaban-con-mail-ya-no-832270/
Yo no he contactado con el servidor aún. Pero he probado que el envio de email con ese servidor dejó hace unos días de funcionar y no se había tocado nada del código. Probando y probando ví que funcionaba todo correcto en otros servidores.
Si tienes el mismo problema que yo y es el mismo servidor ya vemos por donde van los tiros...
Supongo que habrá que ver que tocaron, no obstante ya estoy más seguro que no es culpa mia xD.
Se van a llevar una buena por mi parte. Si hacen un cambio creo que mínimo avisarlo.
Desde luego no usaba este hosting para los proyectos pero era el que el cliente contrató.
¡No lo recomendaría ya a nadie! No me van estas cosas...
Sobre todo porque ahora un servicio de la empresa se ha quedado sin funcionar... y las quejas sabemos a quien cae.
Saludos xavi2. Ojalá se resuelva esto.