I have been having a similar issue for about six months now. I use a mail gateway for all mail except that going to our other site, which is in Munich, Germany. The connection between sites is a static FW to FW VPN. These emails are routed directly to the other site's exchange server, specified by IP address, and so do not go over the gateway. Only messages bound for the other site fail with the error "Host Unreachable" on an intermittent and seemingly random basis; I cannot see a pattern as far as message size, attachments, etc. Alot of the time the failed messages are actually system replication messages! Mail destined for the gatway always goes fine. The strangest part is that other mail will be delivered to the Munich site without a problem while one message sits in the Outbound queue, refusing to be sent and returning the error "Host Unreachable"!
So IP routing or DNS do not seem to be the issue. I should note that the Munich site has seen none of these problems. This looks like a software bug to me. When I drop one of the failed messages into the Pickup directory, it fails immediately and returns an error saying that there is either no From address (not true) or it is not a valid 822 message (822 being the RFC for SMTP). Could it be that the MTA is corrupting messages? Being at the end of my rope, and with my users wanting to hang me with the other end, I am preparing to rebuild my Server this weekend. I have already applied all patches, and recreated the IMC to no avail. Can anyone save me from spending Saturday in the office?