Sorry, just off the top of my head...
Is the WAN port configured and working properly? Is the IP address of the mail server configured or domain name? if domain name, are you using internal resolution or corporate DNS? Is the IP address of the mail server in the same subnet as the MAS server? Is the subnet of the mailserver setup in the trusted networks with the wrong gateway?
If you SSH in and login as root, can you do a ping <DN/IP address of mail server> and tracepath <DN/IP address of mail server> ? (the command might be traceroute and not tracepath, can't remember)
If it is really just going out the wrong port, you can make a static route statement in the MAS server GUI to make that IP use a specific gateway.