Exchange should only route mail for which it is both the authoritative domain and the users/mailboxes are present in the organization. Allowing external mail routing on an Edge Transport role opens the Exchange server to both spam abuse and malicious activity.
Solution
Make sure 'Restrict Accepted Domains' is set to Authoritative Domain (default).