It depends, and it might not be possible.
The issue is often that Outlook clients will cache an "Exchange string" which references the actual mailbox associated with an email address. And, much like you can't recreate a deleted AD object by making a new object with the same name (because the SIDs and GUIDs will be different), you can't recreate a deleted Exchange mailbox by making a new user with the same name and email addresses.
If this is the source of the issue, the only solution is to have the sending user delete the auto-complete entry. If it's something else, well, Exchange NDRs are pretty horrible, so you'll probably have to use the message tracking features to hunt down the email that generated your NDR, and see which email addresses it sent to.