Sounds like un-updated DNS or MX record, do you have root access to the mail server or the machine. What is the network topology - the mail server resides where, you telnet where, where's the SMTP, mimedefang implemented for example ? Please be more detailed.