Many mail servers perform a Reverse DNS lookup on the originating IP address of an incoming SMTP connection. If the result of such lookup fails or the result does not translate back to a proper hostname (one associated with your domain), the SMTP connection will either be rejected, the mail will be deferred, or it will be accepted and treated as possible spam (that is, placed in a Spam Folder or Junk Folder). Reverse DNS lookup is defined by setting up a DNS record of type “PTR “that maps an IP address to a hostname. See FAQ: “How to setup and verify Reverse DNS Lookup” for more details.
It is also important to check whether the rejected IP address appears on one or more blacklists (e.g. via http://www.dnsstuff.com) and if so, request removal from such lists. Run a thorough scan of the computers on your network to detect and remedy any computers that might be compromised (i.e. acting as a “zombie” for sending out spam). Contact the postmaster of the receiving mail server, and discuss the issue with them. These reputation-based systems (aka blacklists) are problematic at best and even those that operate them advise not to rely on any single one for making a determination if an e-mail should go through or not.