If you're willing to risk going over a vague TOS restriction (no "excessive" usage), try fusemail.com.
If you want to pay for certainty, some standard SMTP services are: Sendgrid, AuthSMTP, fastmail.fm.
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.
We use AuthSMTP.
We're going to be using SendGrid http://www.sendgrid.com
I remember having a problem with this when I set up an ec2 instance. I don't have any links handy (it was over a year ago), but I remember getting some helpful responses from gmail when my server attempted to send mail to their users. Something about being Greylisted or maybe I'm remembering that it came through in my postgrey logs.
The best I can remember for my solution was to get an elastic ip, then fill out some forms with a watchlist organization, and add some fancy txt records to my dns.
A couple days later emails were going out fine.
Sorry I can't be more specific, but it was one of those things that hat me beating my head against a wall for a few days, and after a few days of the steep learning curve for sending email the number of things I tried vastly exceeded the number of things that worked, so my notes are of little help.
We have Postini already, so we decided to relay through them. Also, I noticed that my emails were blocked before I had an elastic IP, but after I got an elastic IP address they weren't. YMMV.
I'm not sure who to recommend you to for an immediate solution, but it looks like Amazon is in the process of putting together an in-house SMTP service: http://mailchannels.com/contact/ec2-outbound-inquiry.html