[Exim] Cannot deliver mail to hotmail.com

Any mail I try to send to a valid hotmail.com address fails to deliver
with the reason "all relevant MX records point to non-existent hosts".
This, AFAICT, is naturally not true (dig hotmail.com mx looks fine).

I have never experienced this problem sending mail to any other
domain. I'm running exim 3.32.

Any ideas what the problem could be?

--
Brian Nelson <nelson@???>