You'll get an IP address for your outbound traffic which is "clean", monitored and registered with a ton of ESPs. You can also use Mailgun as a proxy for your incoming mails as well, for spam filtering or custom routing purposes.
Moving to a self-hosted solution (even a US one) offers you more privacy protection options than Gmail/Hotmail, that's for sure. But since physical access is everything, using a US-based VPS provider means there is only a small speedbump between the government and your mail. Using a US-based service like Mailgun, while extremely cool, removes even this speedbump, since they will presumably be forced to cooperate in the same way that Google or Yahoo do.
The best option would be to host your own mail with a VPS with a very strong privacy record, explicit statements about not cooperating with US inquiries, based and hosted in a country with strong privacy protections.
By the way, I still feel that Sendmail has to have the worst configuration file I have ever seen.
Outbound : Use a smarthost.
I host my own mail. I use OpenBSD as my Firewall/Router so it was a simple decision to use the spamd daemon on it for greylisting. The SMTP destination sits on a CentOS machine behind the OpenBSD gateway. I see a spam message maybe once every week or two. I have also used MailScanner to do SpamAssassin and virus scanning of received mail at places I have worked. The spam count went down so far I had people ask me if the mail server was down. A little bit of verification showed we weren't loosing legitimate mail, users were just getting so much spam they thought that was normal.
A smarthost solves your outgoing problem. I can't send direct from my home connection because it is a residential IP and that is going to be blacklisted all over the place. I could use my IPS's SMTP server, hell you could use GMail if you wanted. I however, use a VPS I pay for. My SMTP server logs in (password) over a TLS connection (preshared certificates). It only relays for my mail server because of that.
You don't need to use a well known relay, you just don't relay from a blacklisted IP. Don't leave an open relay and don't send directly from a residential IP block and you probably don't have to worry, unless you start sending spam.
http://www.mxtoolbox.com/blacklists.aspx has various tools to give you a view into how other mail servers will view your hosts.
That's hardly a rule. You clearly will end up on a blacklist if you host from home or if your IP is already on a list due to previous spam activity, but of you run off a static IP in a decent colo and have a proper PTR record, it is more likely than not to be all OK.
The 90% of inbound spam is still very effectively trimmed off by greylisting, i.e. postgrey if you are in postfix. I've been running my own mail server for close to 10 years now and it's really not a big deal.
Another problem is you will have to use a third party smtp server, otherwise your mail will be rejected by a lot of email providers.
* Get a "clean" statically allocated IP address.
* Control your forward and reverse DNS and make them match.
* Set up SPF/DKIM.
* Fill out the Yahoo Bulk Email sender form
That last one probably isn't really necessary, depending on how much email you send to Yahoo.com addresses.
1. Only allow email locally (i.e., via webmail and ssh) - which many would regard as a real pain, but I and the few people who use my server have been OK with. IMAP is very useful with this policy, for batch move/send from outbox folders.
2. Set up TLS to only deliver via SSL
3. Advertise both these facts via SPF (I haven't bothered with DKIM)
But this is just for receiving emails (from the outside world), if your IMAP/POP3 server is on the same server as your primary MX you will not have access to emails on the server while the primary is down. You have to find a way to sync your received mail (maildir/mailbox) to two or more servers.
If you decide to implement a backup MX, try to sync your allowed recipients list from the primary because spammers often try to send emails to an MX with a lower priority, and if it accepts all emails for the domain without checking if that mailbox actually exists you could became a source of back-scatter.
1) SMTP was developed for unreliable environments. If you have problems with uptime, your incoming email will bounce around for 5 days before it gets dropped. So assuming you can get your SMTP server running one day out of five, you shouldn't be in danger of losing anything.
2) Contemporary daemons like postfix and dovecot have sane defaults, so even a naive default install should be mostly secure. They're also extremely low velocity, so once you set it up there's not a lot of ongoing maintenance.