Hay varias cosas esenciales para hacer cuando pasa eso:
1) Comprobar si el dominio tiene un registro SPF y está valido para el SenderID de Microsoft
2) Comprobar si tiene un ReverseDNS la IP del servidor
3) Verificar en
http://mxtoolbox.com/blacklists.aspx si está limpio en todas las bases de datos de spam.