You've found that messages to a specific domain are not being delivered by Messaging Gateway, though other mail services can deliver to the domains. The messages remain in the delivery queue with the error:
No valid hosts (unable to make any connections)
Release : 10.7.4
Component : Default-Sym
The Messaging Gateway may cease to attempt connecting to all MX records if a number of initial MX record connection attempts are unsuccessful.
For example, if a domain has 6 MX records, 2 with preference 10, 2 with preference 20, and 2 with preference 30, the Messaging Gateway may not attempt all MX records if the mail servers in preference 10 and preference 20 are not responsive. This is just an example and the actual situation may vary, but the underlying factor is that the initial mail server connections are unresponsive.
This issue has been addressed in the 10.7.5 and newer releases of the Messaging Gateway.