I deleted an exchange mailbox (soft delete by deleting the AD account) and then added their email address to a distro list's SMTP list.
Emails externally are working fine, but emails internally are bouncing back -- even with people that have never emailed the user before.
Exchange 2007
Part of the bounce message
#550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ##