Problema com mail vps

Buenas noches.

Tengo varios vps, pero hay uno que está haciendo que me coma la cabeza de manera rica, os comento lo que pasa:

En uno de los vps, puedo enviar y recibir correos sin problemas de todos los servidores, excepto recibir correos de Gmail, puedo enviar correos a Gmail pero los que recibo en la bandeja de entrada no llegan.

Es bastante extraño, porque solo pasa con Gmail, con Hotmail se envían y reciben de manera normal.

¿Alguna idea?

Un saludo y gracias.

Pueden ser muchas cosas, igual mira esto tal vez te sirva -> http://forobeta.com/hospedaje-web/209266-mis-emails-llegan-spam-soluciono.html

Tal vez tengas la ip en lista negra, mx mal o cualquier cosa, luego de leer esa guía nos comentas si tienes todo en orden o no.

Ya lo he solucionado, era problema con los DNS.

Un saludo y gracias.