As far as I can tell, this question doesn't already exist here but if it does then I apologize.
As of January 1st our company name has changed and, as such, our e-mail addresses have changed. The switch has gone off well with the exception of a few weird "5.1.1 User Unknown" errors that some external senders are getting when they attempt to send e-mails to us.
I've spoken to an external consultant to get their take on it and they seem to think the recipients have stale DNS records. The MX records to our server has existed on our external DNS for over a month – the new domain was set as our "Primary" domain on January 1st.
I've managed to get a couple of the error reports from the recipients and they look like this. Any help would be appreciated with this matter
The following recipient(s) cannot be reached:
'User Name' on 13/01/2012 11:07 AM
550 5.1.1 <user@new-domain.com>... User unknown
EDIT : The domain listed above is the "new domain". E-mails sent to the old domain still send without issue. I can also verify that the policy has been set to that user and that the new e-mail address exists within their "E-Mail Addresses" tab.
EDIT 2 : The receiving mail server is running VamSoft ORF for anti-spam. Neither Vamsoft ORF logs or exchange logs show any sign of the e-mails getting to our domain, however when they use the old domain they go through without issue.
Best Answer
The key to troubleshooting this one is going to be getting somebody to look at the logs on the outgoing SMTP transaction at the sender's server. You can try to correlate their failures with your own message tracking logs, SMTP protocol logs, or traffic sniffing, but the best data is going to come from the sender's own SMTP server. If the sender has an IT staff I'd recommend working to get in touch with them. If they don't, then try to get the sender to provide you with the non-delivery reports complete with full transport headers.
You need to know what SMTP server the sender is actually trying to perform delivery to and, from there, you should be able to track down the source of the problem. If they're talking to a server you control then you should be able to get a log of the SMTP conversation, possibly all the way down to a traffic sniff. If they're not talking to a server you own then you need to figure out why they aren't (i.e. stale DNS cache).
DNS lookups cached for wholly inappropriate times aren't completely unheard of, but they're not common either. If you know who the sender is using for an upstream DNS server you might try doing some lookups for MX records for your domain against that DNS server to see what you get back.