Hola IArtigas:
Hacia donde esta apuntado tu registro Mx?, es a un proveedor externo o tu controlas tu DNS?
si es asi verifica, que puedas validar tu registro DNS con un nslookup, si tiene algun antispam que ste filtrando email o un firewall que bloquee entrates
Saludos