Steps to take to improve email deliverability [duplicate]
You'll probably want to look into DKIM as well: http://www.dkim.org/
Yesmail is a mail marketing company that takes care of a lot of these issues.
Other things that you can do are
Run your emails through Spamassassin before sending them, to make sure they don't score too high.
Avoid HTML
Avoid URLs
Make sure your users know to add your outbound email address to the address book or whitelist, and then stick with that address.
Related to the above, try to have just one outbound email address that the messages come from.
Make sure your mailserver's IP address resolves back to the domain name it claims when talking to other mail servers.
Use TLS if possible.
All of the above are basically things that spam filters look for when evaluating a message, so your ultimate goal is to avoid as many triggers as possible.
You could send new customers an introductory e-mail which includes a link to "verify" their e-mail address. This would confirm that your e-mail is not being trapped by spam filters while assuring that the address in your system is valid.
If you don't receive the verification, you can then take further steps to rectify whatever reason that customer is not receiving your e-mail.
Get onto the ISP's feedback loops for spam complaints - and action those complaints (basically, if someone hits 'report spam' instead of unsubscribe then don't email them again) - details of the big ISPs are here: http://blog.wordtothewise.com/ISP-information/
Make sure bounced emails are removed from your mailing lists. We use a neat piece of software called bbounce but googling for it I think they've pulled it now - was owned by the Whitaker Firm LLC
We looked into Goodmail's certified email program which provides whitemail listing for Yahoo and AOL (and some others) but they weren't interested! (our total email volume is less than 50,000/month and we currently use an ESP not on their list). I had a very helpful conversation with a sales guy at StrongMail who thought Goodmail was probably overkill for our volumes.
Plus make sure that your emails have the location address of the organisation/sender in the email and an easy to follow unsubscribe link. I swear I've read somewhere industry insiders reporting that the content of emails are checked for this sort of content and factor into the deliverability equation - if you're not already, check out Mark Brownlow's excellent No Man is an Iland website.