We use SendGrid: http://sendgrid.com/
They've got a free account for up to 200 mails a day.
I've set up a number of mail servers for myself and clients. I've always asked providers upfront to guarantee that I can get assigned to a new netblock if any of the IP addresses they give me show up on any blacklists. In some cases, just asking resulted in getting clean IPs from previously unused netblocks. In the few cases where the IPs were blacklisted, I got new ones without any problems.
Nearly all providers will give you a new IP if your old one got blacklisted before it was assigned to you.
Note; 'clean IPs from unassigned netblocks' are not necessarily good. see bogon filtering[1] - still, running your own mailserver is not an impossibly difficult task.
AuthSMTP is priced with a fixed number of "email From: addresses", but what they don't tell you on the pricing page is that you can add a whole domain (wildcard *@domain.com) and it just counts as one address.
Looking at their pricing page it looks like you'd be out about $150-160 bucks per year. Up to you to decide if it's worth it, but hardly expensive in the normal sense of the word.
That works great until a spambot decides to start spamming <1000 common usernames>@yourdomain.com
Isn't that what SPF is designed to protect? They'll never get through if you have a strict SPF record that lists AuthSMTP as the only email server for your domain.
I haven't experienced getting added back to a blacklist off a significant webmail host after being taken off one. Once your IP is in the clear, it'd take some abuse to be put back (anecdotal). These 3 steps usually get me unblocked if starting with a bad IP:
1. Set up reverse DNS for your IP address
2. Publish an SPF record
3. Check the Spamhaus lists http://www.spamhaus.org/query/bl?ip=1.2.3.4 and request removal if your IP address is on them.
As an addendum to grandparent: extremely comprehensive guide to postfix + dovecot here: http://workaround.org/ispmail
Spamhaus is one list. There are hundreds. (See http://www.dnsbl.info/dnsbl-list.php for starters) Some are nearly impossible to get off of.
Been there, done that, didn't work. We don't even know why GMail was black-holing our mails, but we did everything on their suggested list for getting out of the world-o-pain and still often our mails were landing in the spam folder, hence the switch to SendGrid.
If anyone has any suggestions to get around this sort of limitation, I'm all ears and will be back on Zimbra before the weekend is out ;-)