[Exim] Unrouteable Mail Domain - Why??

Hi!

I have just a small question:

Sometimes our Exim-Mailserver (3.36 on RedHat 7.3)
can't send out mail to some domains.
This is the latest problem:

[root@rzvemgw msglog]# exim -qff -v
Single queue run
LOG: 0 MAIN
Start queue run: pid=882 -qff
delivering message 17h499-0000BP-00 (queue run pid 882 fd 6)
LOG: 0 MAIN
Unfrozen by forced delivery
LOG: 0 MAIN
** Tine-v-H@???: unrouteable mail domain "t-online.de"
LOG: 0 MAIN
Frozen (delivery error message)
LOG: 0 MAIN
End queue run: pid=882 -qff
[root@rzvemgw msglog]#



When I do a nslookup on those domains which exim can't route
everything works fine, I can see all the MX-entries and so I don't
understand why this happens.
Can somebody please tell me why?

Michael