[RobGR]

What you really need is an smtp relay, on a fixed IP, carefully configured to relay only from your hosts and on a reputable block of IP addresses.

That is entirely possible. The server itself does not have to be very extreme, the lowest end Rackspace cloud or Godaddy server should do it, it all just comes down to if those IP addresses are blocked too.

The real problem is that you will spend too much time figuring out reverse DNS, SPF records, and all kind of email trivia. I'm not sure it's really worth it. How many customers do you lose if you just ignore the problem ?

If you can't just ignore the problem, get a host on a reputable block of IPs and hire a freelance sys admin to set up and baby the system. You will want to monitor bounce rates and other metrics and fix problems as they arise.

[jsatok]

I was seeing a relatively high (30% or so) open rate on emails, but knew there was a deliverability problem because friends and family were reporting not getting my daily emails (my site automatically sends out an email every day at 9am). I'm now using SendGrid, getting an open rate of over 50% (yeah, it's nuts!), and I don't need to worry about DNS, SPF, etc. I highly recommend SendGrid.