No se reciben correos de algunos dominios

Hola, que tal? Aquí estoy, pero ahora con otro problema.  :-(
Hace una mes aproximadamente cambié de proveedor de hosting de mi dominio. Desde que hice este cambio, está pasando que ninguna cuenta de correo de mi dominio recibe correos de algunos dominios en particular. Mi proveedor dice que no es problema  nuestro, que tiene que ser algo de los servidores de las otras empresas (como que tienen algun filtro por IP, o algo similar), y que ellos no pueden hacer nada.
A mi eso no me convence, la verdad. He hecho un dnsreport de mi dominio y me da error en los siguientes apartados:
Mailserver connection test HELO, MAIL FROM, RCPT TO, QUIT: Connect to mailserver FAILED (could be greylisting)
Mailserver greeting: The server should have an A record which points to the mailserver for the hostname which is presented in the greeting
Pero lo cierto es que no sé lo que significa. Ni si tiene alguna relación con mi problema.
La verdad es que no se qué hacer, si pedir que me cambien el servidor de correo, o que.
cuál podria ser la causa de este problema?

Veamos si he entendido el problema y analizar los posibles fallos, para encontrar las soluciones.
Cambiastes de un proveedor de Mail a otro, conservando tu nombre de dominio, y ahora, no te pueden enviar correos, esto seria la sintesis.
Bueno, ahora los problemas que pueden haber en este tipo de procesos. Para esto ha habido una transferencia de DNS de un proveedor a otro, (sobretodo que tu sigas siendo el owner del dominio), y esto implica que las DNS se tengan que actualizar, dado que variara la IP.
Por el mensaje que pones, es como si no se resolviera el servidor de correo, su registro A (que es el de Host) y por ende los registros MX (mailbox)
Por lo que comentas en la segunda parte, si que te resuelve correctamente dentro de los mismos servidores DNS, por lo que internamente todo funciona correctamente. Ahora bien deberias probar desde otros servidores como Hotmail, Yahoo, Gmail, dado que estos, por el servicio que ofrecen a millones de usuarios, no tienen problemas de configuración. Si con estos te va, el problema es de tu cliente que algo tiene mal configurado con su resolución de nombres hacia tu dominio. Si por el contrario no va, posiblemente haya algún problema con el traspaso del dominio o con los servidores DNS hacia el exterior (posiblemente las transferencias de zona, resolución de los registros)
En fin, prueba el envio de los servidores mencionados y si así funcionan la pelota esta en otro tejado ;)
 

Sin duda tu correo tiene un 90% de probabilidades que vaya bien. El 10% me lo reservo por si, extrañamente o por casualidades de la vida, podria pasar lo siguiente:
El dominio de tu remitente está bloqueado por tu proveedor.
La IP de tu remitente, o la red, esta bloqueada por tu proveedor.
Pero como has dicho tu proveedor ya te ha dado a entender que todo está correcto, así que yo diria más que es probable que le pase algo a ellos.
Posiblemente lo de la IP al DNS, no es normal pero podria ser, y igualmente los casos anteriores aplicados al destinatario.

Excelente. Una fantástica solución.

Excelente. Una fantástica solución.