I admit this has been in my "If you don't look at it funny, it will not mess with you" category.  However after having some interesting conversations at Ignite last week I decided to go back and look at this.  

Occasionally I have a user that reports the "IMCEAEX" NDR.  I have always had them delete their address autofill cache and the issue was resolved.  Our mailboxes have X.400 addresses assigned.  They have been there since I took over the environment.  There are no X.500 addresses.

I ran the following to see if there are issues I was not aware of:

Get-TransportServer | Get-MessageTrackinglog -EventID FAIL -Start (Get-Date).AddDays(-7) -ResultSize Unlimited | Where {$_.Recipients -match "^IMCEAEX*"}

This returned a large number of results.

My question is, do I need x.400 addresses?  Should they be x.500?  Would removing the x.400 resolve these NDRs or possibly make it

Hi ,

Please create the X500 address by using the NDR received on the sender mailbox and then add that x500 address to the recipient mailbox to whom the mail has got bounced.

Below is the link to create the X500 address by using the NDR received at the sender end :

http://msexchangeguru.com/2012/03/15/x500/

At the same time please have a look in to the below mentioned blog.

http://eightwone.com/2013/08/12/legacyexchangedn-attribute-myth/

Should I remove the X.400 addresses?

Is it best to add X.500 to the Address Policy to automatically add this address?

Do you think it would be ok to script the removal of X.400 and addition of X.500 across the environment?  I'm a little confused as to where these addresses come into use.

Hi,

It should be X.500, not X.400. X.400 addresses aren't used unless you have an X.400 connector or some such, but hardly anyone uses those anymore.
Please refer to below link to Create an X500 proxy address for the old LegacyExchangeDN attribute for the user, for your reference:
https://support.microsoft.com/en-us/kb/2807779