Make sure your MX record correctly points to your server IP. If you can provide the domain name I can check what IP address it points to or you can use MXtool box to do this. Also have you tried to telneting out side your network to make sure there is no firewall that may be blocking incoming connects?