Most firewalls generally have an NAT rule and Access rules (or ACLs). NAT stands for Network Address Translation. This translates IP addresses from one network (e.g. your internal network) to IP addresses from another network (e.g. external IP addresses provided to you by your ISP).
Check your firewall configuration for the NAT rule that maps your Exchange server's internal/private IP address to an external/public IP address. Does it still point to the server's old IP address? If yes, you will need to change it to the new IP address.
Also make sure any Access rules/ACLs that allow inbound SMTP traffic work correctly and allow SMTP to the server's new IP address.
Unless the above steps are performed, your Exchange server -- which hasn't really changed as far as your Exchange Organization, Active Directory, and (for most part) internal users are concerned -- is not recognized, or appears as a completely different server to your firewall.
This was first published in July 2006