Tenes el domainkeys y el spf configurado en el servidor o para el dominio con problemas. Te fijaste el log del exim para ver si hay conexion al menos.
Intenta de cambiar el puerto de tu outlook ya sea de 25 a 26 o al rebes, y recuerda marcar la casilla mi servidor requiere autenticacion