If you could post the domain name that this server provides service for, or PM me a test mail address, I can setup a watch on my server when you try to send to it and probably tell you what the problem is. As Soulwatcher says, the most common problems are connected with missing RDNS entireis and the server not having a hostname. But also, check that the server uses a fully qualified domain name in its EHLO and that it is not configured as an open relay. If it is an open relay, then the chances are that your server has been used for spaming, and it is now listed in a DNS blacklist.
You might also want to try running the main domain through the checks at
http://www.dnsreport.com it will usually give you a pretty good idea if there is a DNS related problem causing mailserver issues.
