After I recreate a user's mailbox by extracting the email to a .pst file, then deleting and recreating the mailbox, anyone who replies to a message from that user gets a nondelivery report (NDR) that includes what looks like the distinguished name (DN) for the mailbox. What causes this NDR?
This situation occurs when a respondent to an email message has an old pointer to the recipient's mailbox name. Microsoft Outlook stores a unique ID that represents the DN; recreating the mailbox generates a new ID, but other users still have the old ID in their mailboxes. You'll see the same situation if you use ExMerge to move users from a server in one organization to a server in a different organization, even if their SMTP addresses remain the same. To fix this problem, tell users to select the recipient name from the Global Address List (GAL) instead of just clicking Reply. The bigger concern, though, is why you're deleting and recreating mailboxes—that sounds like an odd procedure that you should perform only with good reason.