I've looked into this a bunch as we've been building Nylas. Our backend is essentially a cloud mail user agent (MUA), but can have similar issues to a MTA or ma

I've looked into this a bunch as we've been building Nylas. Our backend is essentially a cloud mail user agent (MUA), but can have similar issues to a MTA or mailbox provider. It turns out that creating a successful product in the email space requires you to build relationships and partnerships with the existing vendors/providers. It takes a lot of work, and is part of what you pay for when using Mailgun/Mandrill/etc. These "greylists" and systems that drop mail from unknown IPs have been pretty carefully designed and tuned to combat the insane amount of spam out there. They work remarkably well, and for most of today's email users, spam is no longer an issue. (The current state of email abuse innovation is promotions/marketing/etc. which is a more subtle challenge.) At the end of this article, the author writes, "This isn't how the internet is supposed to work." Ironically this system of obscure reputation-based email is a direct result of how the email system was actually designed to work, with a total lack of permissions or feedback loop. Many SMTP servers used to not even require a password. Stuff like DKIM/SPF and DMARC is a step in the right direction. But the RFCs upon which our email system is based were written decades ago, and in many cases have fundamental flaws, like SMTP leaking metadata no matter what. I could go on and on about issues with email, and why I care about getting them fixed, but let's just say it was designed in a different era of Internet with different constraints and opportunities. So how do you build a new email service and not get blocked? Well, you spend a few weeks or months emailing, calling, Skyping, and meeting with folks in the current space. You work your way up through marketing support and random protocol discussion lists until you are talking with the folks who can influence which IPs are blocked/unblocked. Then you convince them you are (1) building a legit venture, (2) are worthy of their trust, and (3) don't directly compete with them. Then you'll get a small number of clean IPs and you must not screw up! There are a few hacks, like sometimes a single partner/vendor will sell you a block of clean IPs and help manage the spam reputation. But usually it's just a lot of sweat and annoying phone calls. It takes way, way longer than setting up SPF/DKIM. The challenge is more relationships than technical. Once you have a new email sending provider, the burden shifts to you for doing abuse/spam prevention. And you find yourself implementing many of the strategies and systems you cursed when getting started. But that's the circle of rfc2822 life I guess. Oh, and never use EC2 IPs for sending mail. Most of them have been burned by spammers.