First off, are you using the default mail server MailEnable or are you using another email server?
If you're using MailEnable, do you have the DNS configured to try to an external DNS server or have it set to the default 127.0.0.1? (you can check that by RDP-ing into the windows server and going into the MailEnable management console, navigate to Servers > localhost > Services and Connectors, right click on SMTP and go into Properties, look at what's set for DNS Address(es).)