In a mixed Exchange 2007/2003 environment with a Connector to a Non-Exchange System on an Exchange 2003 Server you cannot send messages from Exchange 2007 to a recipient in the Non-Exchange System if the following two conditions are true:
1) the Connector contains an Address Space with an underscore ("_") in it, like in the following example:
2) one part of the address of the final recipient (for example, the "Domain"-part) matches this Address Space.
In this case, the sender of the message will receive a Non Delivery Report from the first Exchange 2007 Hub/Transport-Server and the message will not be routed to the recipient.
The Non Delivery Report contains the following error-information:
#550 5.4.4 ROUTING.NoNextHop; unable to route
This error is returned despite the fact, that the Scope of the Connector is set to "Entire organization" and the Address Space is visible in the Routing Log Viewer in Exchange 2007.
Please note, that this issue can occur in conjunction with all EDK-Gateways for Exchange 2003 and hence is not limited to the Lotus Notes Connector for Exchange 2003.
You can work around the problem by re-defining the Address Space in question so, that the underscore is eliminated from it and replaced by a wildcard. One possible solution for the example above would be, to replace "abcd_ef" by "abcd*". As soon as this change has been replicated to Exchange 2007, the problem is resolved and messages can be sent from Exchange 2007 to the desired destination.