I've got a head-scratcher here. We are merging with another company and the initial decision to let us create a forest trust and each run our own domains has been reversed and we are now migrating their users into our domain.
We had set up their Outlook clients with both email addresses and they have been co-existing happily for about a month. What we're seeing after migration is that users are randomly sending out NDRs for the email address at DomainB. Most emails go through, but some don't. Sometimes, it's obvious: a reply-to from an email with the pre-migration DomainB address, but sometimes, it happens on totally fresh emails (pulled from the address book, the AutoFill addresses have been purged).
The bounceback looks like a typical X500 string I'd expect to see, except that the recipient CN is all over the place. Sometimes, it's a straight GUID, e.g. cn=9c97ce80c17947b8851244d62fc09bab, but sometimes, it's got part of the username in it: e.g. cn=9c97ce80c17947b8851244d62fc09bab-Lastname, First-3-letters. It never matches the LegacyDN value in the Active Directory object.
I can add the X500 string from the NDR and it works. What appears to be impossible is predicting the X500 CN value for the Recipient. Since it's random, I can't always make it happen after migration and then someone's client gets an NDR and we have a Situation.