The company I'm working for previously bought a small company who had their own e-mail service via some provider. And now when we're trying to merge them to our domain, we get this error message when we try to send an email to the old address via gmail for example.
What we've done is this: - Add the old email address as an alias in our Exchange - Disclose the email service form the old email provider
When we send an email to the old address via our own Exchange, the email delivers just fine. Just not externally, via gmail, yahoo, hotmail etc.
What is the cause of this? Could it just be a DNS sync issue? That is fixes itself over time?
What version of exchange are you using ?
Apart from changing MX, you need to create Recipient Policies / Accepted Domain in your Exchange.
Just changing MX wont work. MX Change will forward emails to your IP, but your exchange server has to be configured to accept emails and forward it to relevant mailboxes.