Hi
The problem was made worse by the fact that we had left the response code for a reject due to unknown recipient as 4xx, so naturally one of these emails resulted in many connection attempts if they came from a real mail server (as opposed to a zombie). At one point we were up to 500 connections per minute. The solution (in our case) was to set the response code to 5xx and accept the risk that mail will be rejected if the backend LDAP containing the mailbox names goes offline.
What's really funny is when you set the MX of the domain to 127.0.0.1, so the mails bounce back to the postmaster of the offending server(s).
Daniel