Hola,
No das muchos datos para saber por donde pueden ir los tiros. Prueba de comprobar que el Servidor de DNS no te da ningún error (
http://www.dnsreport.com/) y sino, tendrías que dar algún dato mas.
¿El Hospedador no te ha contestado?. Que lástima que los Soportes Técnicos de algunas Empresas sean tan "flojitos"
.
Si quieres que mire alguna cosa mas, dime por el privado el dominio de los e-mails que no recibes y miro a ver si puedo ver algo mas.
Suerte