My Exchange server here at work is behind a PIX, and then a Nexland DSL router with firewalling capabilities. At first I thought the PIX "fixup smtp" might be damaging the conversation somehow, but of course I turned that off long ago (and it shouldn't affect outbound anyway).
Answer: The Nexland has a setting:
Allow IDENT Port []Enable []Disable Note: Makes port 113 seem closed, not stealth
Setting this to 'Enable' fixed the problem.
I still need to find out now how to get Exim to not care whether this is set or not, because I'm sure I'm not the only one who has had this set, and I'd rather not miss anyone else's valid mail.