The first thing you should check is to see what name servers are handling your domain and its MX records.
The most common problem with these is a “split” DNS where the inside and outside world are referring to two different name servers, each with different definitions.
Use nslookup or dig to specify the different servers and do an SOA (Start Of Authority) for your domain for your internal and external name servers (called forwarders), and verify that they point to the the same server as a source of the zone file.
Another common problem is when the name server’s A record does not have a matching reverse lookup (PTR record). Some places (AOL is known for this) will not do email with a mail server that doesn’t have a reverse lookup in an effort to reduce spam.
Hope that helps,