Exim's receiver verification feature is very useful - it lets Exim reject unrouteable addresses at SMTP time. However, this is most useful for externally-originating mail that is addressed to mail in one of your local domains. For Mailman list traffic, mail originates on your server, and is addressed to random external domains that are not under your control. Furthermore, each message is addressed to many recipients - up to 500 if you use Mailman's default configuration and don't tweak SMTP_MAX_RCPTS.
Doing receiver verification on Mailman list traffic is a recipe for trouble. In particular, Exim will attempt to route every recipient addresses in outgoing Mailman list posts. Even though this requires nothing more than a few DNS lookups for each address, it can still introduce significant delays. Therefore, you should disable recipient verification for Mailman traffic.
Under Exim 3, put this in your main configuration section:
receiver_verify_hosts = !127.0.0.1
Under Exim 4, this is probably already taken care of for you by the default
recipient verification ACL statement (in the RCPT TO
ACL):
accept domains = +local_domains endpass message = unknown user verify = recipient
which only does recipient verification on addresses in your domain. (That's not exactly the same as doing recipient verification only on messages coming from non-127.0.0.1 hosts, but it should do the trick for Mailman.)