From what I've heard and seen, DO, EC2, and Linode address blocks are more likely than not to be blacklisted by default. For transactional mail, you're much better off using something like Mailgun, Socketlabs, or Sendgrid. Some amount of marketing emails can also be sent through those services, but if you don't fit within the patterns they support, and if you're confident in taking control of your own mail reputation, you'll want to look at lesser-known VPS hosting companies whose IP blocks aren't blacklisted.
Aren't providers supposed to prevent this?
Sorry/Uzuojauta.
Tying assessments of trust to IP addresses through blacklisting is crude mechanism, and becomes more and more susceptible to type 1 errors as demand on the v4 address space reduces the time between address reassignment.
But it's an easy mechanism to implement, so basically nobody using it wants to admit it's flawed or learn to deal with it's unreliability.
