Usually this error comes up when a mailbox has been restored. Pull the ICMEAX line from a NDR email and enter that text when prompted after running the powershell script below. At which point you can add the X500 address in to the users mailbox as an extra address. Make sure that you put in X500 as the type not X.500 as exchange 2013/2016 have in their examples. Alternatively you can paste the whole string from the powershell ad an additional proxyaddress in the users AD account.
$Direction = Read-Host “ENTER IMCEAEX”
$Replacement= @(@(“_”,”/”), @(“\+20”,” ”), @(“\+28”,”(“), @(“\+29”,”)”), @(“\+2C”,”,”), @(“\+3F”,”?”), @(“\+5F”, “_” ), @(“\+40”, “@” ), @(“\+2E”, “.” ))
$Replacement | ForEach { $Direction = $Direction -replace $_[0], $_[1] }
$Direction = “X500:$Direction” -replace “IMCEAEX-“,”” -replace “@.*$”, “”
Write-Host $Direction