When migrating from on-prem Exchange to Office 365, it's best to treat it like any other cross-forest move and populate each object's LegacyExchangeDN value as an X500 address, otherwise you'll get NDR errors replying to old messages or calendar entries once mailboxes start moving.
When receiving IMCEAEX NDRs, you can use the contents of the error to determine the missing X500 and then add it back to the proxyaddresses array for the object and let that sync to O365.
Example :
IMCEAEX-_O=ForestA_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FHSDHJF23GHYED+29_CN=RECIPIENTS_CN=John+2ESmith@namprd01.prod.outlook.com
Resolution :
Remove IMCEAEX- and replace with x500:
x500:_O=ForestA_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FHSDHJF23GHYED+29_CN=RECIPIENTS_CN=John+2ESmith@namprd01.prod.outlook.com
Drop the @xxxxx from the end
x500:_O=ForestA_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FHSDHJF23GHYED+29_CN=RECIPIENTS_CN=John+2ESmith
Replace _ with /
x500:/O=ForestA/OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FHSDHJF23GHYED+29/CN=RECIPIENTS/CN=John+2ESmith
Replace +20 with spaces
x500:/O=ForestA/OU=EXCHANGE ADMINISTRATIVE GROUP +28FHSDHJF23GHYED+29/CN=RECIPIENTS/CN=John+2ESmith
Replace +28 with (
x500:/O=ForestA/OU=EXCHANGE ADMINISTRATIVE GROUP (FHSDHJF23GHYED+29/CN=RECIPIENTS/CN=John+2ESmith
Replace +29 with )
x500:/O=ForestA/OU=EXCHANGE ADMINISTRATIVE GROUP (FHSDHJF23GHYED)/CN=RECIPIENTS/CN=John+2ESmith
Replace +2E with a period (.)
x500:/O=ForestA/OU=EXCHANGE ADMINISTRATIVE GROUP (FHSDHJF23GHYED)/CN=RECIPIENTS/CN=John.Smith
Just take this value and add it to the proxyaddresses array of the user in Exchange Onprem, sync to O365 and bam!