It may be a DNS problem of some kind, can you turn on more debugging logs on the mail server?