Yes, mail is flowing properly to and from our old server on port 25. We have had an exchange 2007 server running on win 2003 for many years, through the same firewall, same isp, etc
The issue is unique to our new server. We have duplicated all of the firewall settings, and even trying it through a completely different firewall with no luck.
You are able to connect internally, so that means the Transport Service is listening on port 25. When a telnet command comes in Exchange doesn't differentiate between an internal or an external address. It just answers the request coming in.
That being said, Exchange and Windows firewall seems to be ok. Do you have any other software firewalls installed on the machine that might cause some conflict?
The problem is either you need to tell your ISP to allow port 25 on the public of IP of your Exchange Server, your firewall rule is incorrect (meaning either the NAT is incorrect or ACL is not configured properly), or your rule is connect and your firewall
is not honoring it (while unlikely still possible).
Best bet is to look at the firewall logs, if you see the request come in and get blocked ,the issue is at your firewall. If you do not, then the issue is at contained to your ISP.