This is why we test things before going live:
After migrating a test box from the old Exchange environment, it could receive mail just fine, and sending mail out of the organization worked flawlessly too. Unfortunately any mail sent from this account to recipients within the old Exchange environment got stuck in the mail queue.
Logically as usual, the fix was to complement the default receive connectors on the old servers with the explicit addresses of the new Exchange servers, even though they naturally were well within the 0.0.0.0-255.255.255.255 range. Way to go, Microsoft!