Hoople - 1:18 am on Feb 3, 2011 (gmt 0)
Is your IP in a Netblock marked as 'Portable' ie in a dial up range? Comcast, many F100's and a few Tier 1 ISP's won't accept mail from any portable/dial up range.
Check your IP on [mxtoolbox.com ] This test will check a mail server IP address against 147 DNS based email blacklists. Whitelisting on the recipient end is sometimes the only option for those lists with no reasonable removal process.
As an email admin by day I suggest you do more than just the reverse dns. That was enough in 2006-2007, the spammers have got that covered since then too. Add to the dns SenderID/Domain Keys and SPF records. There has been no harm in doing both SenderID/Domain Keys and SPF IMHO.
The best of the online SPF record checkers is [kitterman.com ] There are others but they give confusing results (IMHO) and/or false errors. openspf.org has lots of backing docs if you are curious.
Some SPAM blacklists will list you if your server banner (greeting) doesn't match your domain. On a shared server this may not be configurable. You then may find some relief by listing it as a secondary MX record (in addition to citing its IP in your SenderID/DK/SPF config)