Efficient router rejecting NATed mail server connection

[Whit Blauvelt]

I'm told from the other end that they don't think they have any special
rules in their routers. Maybe a router upstream? I can't see why else
attempts to connect from behind netfilter NAT (by mail server or telnet) to
port 25 on their mail servers gives "no route to host", while port 23
connects (to their routers), and other ports give "connection refused".
Meanwhile connections from our firewall (not behind NAT) work fine to their
port 25. In both cases we're coming from the same public IPs.

We have no problem at all connecting to anywhere else with this setup - and
send a reasonable amount of mail out. Switching from SNAT to MASQUERADE in
netfilter makes no difference, either.

Has anyone seen this before? 

Whit