Postea la configuracion de tu exim.
Pasale esta prueba:
www.abuse.net/relay.html y fijate en que prueba detecta que puede enviar emails. (y postea los resultados)
Decinos en que distribucion y version de Linux tenes instalado el Exim, la version de exim, etc.
Solo si brindas la informacion necesaria te van a ayudar.
Saludos