What happens if you try telnetting into your mail server from your local computer?

try something like this:

telnet mail.yourserver.com 25

when it responds, type "ehlo mail.yourserver.com" (hit enter)

then paste the output here. (type quit to end the telnet session)

A typical session should look like this:

telnet mail.whatever.com 25
Trying xx.xx.xx.xx...
Connected to mail.whatever.com.
Escape character is '^]'.
220 mail.whatever.com ESMTP Postfix
ehlo mail.whatever.com
250-mail.whatever.com
250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-STARTTLS
250-AUTH LOGIN CRAM-MD5 PLAIN DIGEST-MD5
250-AUTH=LOGIN CRAM-MD5 PLAIN DIGEST-MD5
250 8BITMIME

At the end I got this:

250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-AUTH LOGIN PLAIN
250-AUTH=LOGIN PLAIN
250-ENHANCEDSTATUSCODES
250-8BITMIME
250 DSN