Have you checked if you are listed on any RBLs?
> I have the same situation - and it is not related to exim I think. So
> far I have identified 7 servers that refuse smtp-connection to one of
> our three mail servers while it is not the case with the other two. I
> can for example telnet to most of those servers on port 25 from
> maties1 and maties2 but not from maties3.