I moved a small client from one hosted Exchange server (Microsoft Office 365) to another (Intermedia.net). Some emails from External senders to the users on the new server host are undeliverable, bouncing off the OLD server w/ no relay errors.
It seems like the typical error that you get with LegacyExchangeDN or X500 addressing that requires the clearing of the name completion cache. However in my experience that occurs for internal senders. This is from external senders, who pretty much all are Outlook users. The rejection to external users is coming from the old server as affected external senders emails are still delivered there. However our MX records have fully propagated and no one who is not on Outlook, or is a new sender and has no correspondence history, has a problem emailing us. Is it possible/likely, the same name completion/clear cache error? I'm going to have to reach out to users and IT admins around the country and walk them through resolving this issue so their users can email us again?
UPDATE: Our DNS on Godaddy had a default 1 Week TTL on MX records. SO both our legacy record and the new record I created on Friday evening had a 1 week TTL. I just changed it to 30 minutes, but I suspect we might be out of luck until 1 week from the original Friday evening change? One of the big spots forwarding email to the wrong server is from users whose providers go through messagelabs.com (Symantec) servers.