Problem:

Some mail servers are unable to route to #######@subdomain.domain.com

In this environment, the Windows based Domino servers were affected, but the Linux based Domino servers were not. It turns out that the affected servers are those running Microsoft Windows server operating systems, and of those, only those sites where the local dns domain use a "default" address for misspelled or incorrect server names within the domain. In other words, those where typing wwww.domain.com would work just as well as www or even noplace.domain.com. It's a valid configuration, but not used in all cases.

Cause:

The remote site does not have an "MX" (mail exchange) record in their DNS configuration for "subdomain.domain.com".

The Microsoft Windows DNS client lookups use a non-standard approach to name resolution. If a host name is not found exactly as requested, the Microsoft Windows server or workstation attempts to find the server as if it were in the local domain by adding the local domain name to the server named being looked up. That's a fine approach when you're looking for a server address in general, but NOT when you're looking for MX records. This is because it skips a step. First it looks for the MX record for subdomain.domain.com. When it fails to find that, what it should do, is look for ANY record for that address as specified. Since a CNAME or an Address record does exist, that IP address should be used. Instead, the Microsoft DNS server skips that and immediately goes looking for a record for "subdomain.domain.com.localdomain.com". If "localdomain.com" is using a wildcard default to return misspelled requests to their web server, even though that is NOT an MX record, that address will be returned to the application making the DNS request.

In other words, in the lack of a valid MX record which is an exact match for the request, the Microsoft DNS resolver will return a NON-MX answer that it created itself by adding the local domain to the request AHEAD of a NON-MX record which is an exact match for the request. This clearly backwards -- but not something that Microsoft will likely change, given that they've done it that way for 15 years or so.

A walk through example:

Sending mail from "mydomain.com" to "subdomain.yourdomain.com"

1. The Windows based Mail server attempts to send a message to "user@subdomain.yourdomain.com"
2. The Mail servers does a DNS lookup for the MX record for "subdomain.yourdomain.com"
3. No MX record exists for "subdomain.yourdomain.com"
4. Microsoft DNS skips doing a lookup to find a NON-MX (A or CNAME) record for "subdomain.yourdomain.com"
5. Microsoft DNS changes the lookup to find a record for "subdomain.yourdomain.com.mydomain.com"
6. Sites with default (or wildcard) DNS entries in their domain return that default value in this case (e.g. www.mydomain.com)
7. The Microsoft DNS never goes back to check for a NON-MX record that exactly matches "subdomain.yourdomain.com"
8. The mail server attempts to send the message to the invalid address returned for subdomain.yourdomain.com.mydomain.com" and the message fails.
9. Mail isn't delivered.

The behavior is incorrect on the part of the Microsoft server, but that's not going to change any time soon -- it's been the case for nearly 15 years.

What I've done to work around this issue:

Within my own domain, I've had to set up a fake CNAME entry which actually resolves as "subdomain.yourdomain.com.mydomain.com" and points to the address of the other server "subdomain.yourdomain.com.". This way, when Microsoft does the wrong thing, it gets a workable result -- so the mail goes through.

Obviously what I've done is a wierd workaround and not something that most site admins will be willing (or frankly able) to do.

What the remote side must do to really fix this issue

This issue is probably affecting other people trying to send mail. They would likely be failing, but since they don't have any access to the person who manages their mail servers or those people aren't willing or able to track down an obscure issue like this, those users are simply unable to make it work.

The remote side can resolve this issue, by asking whoever manages their DNS to create a valid MX record for "subdomain.yourdomain.com" If they are using a unix or linux based dns server, it will look something like this:
; ------------------------------------------------------------------------------------------------------------------------------------------------------------
subdomain.yourdomain.com. IN MX 100 123.123.123.123
; ------------------------------------------------------------------------------------------------------------------------------------------------------------