So you are running your own mail server then? Check w/ your DNS registrar to see if they support reverse dns lookups. Alot of mail servers use an anti-spam technique that will look up your IP to see if it matches your domain name. Theres alot of registrars that dont support this kind of lookup (and dont tell you!).
I found this out when I came into the company I work for now, and was asked to set up a mail server. AOL is one major one that does this. The way I got around the problem, rather than trying to change registrars, there are companys that offer mail forwarding for pretty cheap.
I use dnsexit.com. So any mail that doesnt pass this test is forwarded through dnsexit.com which passes the test.