1.) In Exchange, open the Properties for the affected user (to which the NDR is refering to). Then click the E-mail Addresses tab.
2.) Click the arrow next to Add and click Custom Address.
3.) For the E-mail address, copy-and-paste the result from above.
4.) For the E-mail type, type in "X500" (without the quotes).
5.) Click OK, and click OK again.
Try sending an e-mail to that user now. It should be working!
Note: this must be performed for each e-mail address affected. The most common items will be replaced. However, there may be other symbols in the LegacyExchangeDN attribute that will also be changed from the way that they appear in the NDR. Generally, any character pattern of "+##" must be replaced with the corresponding ASCII symbol.
More Information: https://support.microsoft.com/en-us/kb/2807779