Yesterday I had my assistant delete a user and create them again as a contact. When I tried to email this person today, I got these NDR’s. Event logs confirmed the NDR. After checking email addresses were correct, I purged the mailbox, restarted SMTP and the Information Store with no affect. After some research, I ended up deleting the contact and created it again. Guess what. It now works. Don’t really know why yet. Perhaps contact was created before user was deleted properly. Will investigate further when I have some time.
In case you want to comment, a brief explanation of our Exchange config might help. We don’t have a common AD domain across all our offices as some are (still) running SBS2003. However, all incoming email to our email domain is delivered to our head office Exchange server. People in SBS AD domains are configured as contacts on our head-office Exchange server. The primary email address for these people is a sub-domain of our primary email domain. These sub-domains are configured on our internal and external DNS servers. This causes the email to be redirected to the SBS servers in these other offices. It works but is not pretty.