It seems you created a new e-mail address for the user as well. If that is the case, just add the old address as an alias for the user. As I recall, you do this through Active Directory Users and Computers. Be sure to use the Advanced view so you can see the exchange addresses, and under the E-Mail Address tab, simply add the user’s previous e-mail address.
The e-mail addressed to the old address will shortly start to be delivered to the new mailbox. You will not be able to recover any e-mail that was lost in the interim.
If this is not your issue, you will need to become a lot more specific about the problem you are hinging, including the text of the NDR users are receiving if they are receiving one.