I've helped friends set up mail servers fairly often, and they've had the same experience. But I wouldn't recommend DO (especially) nor AWS for this.

I'd recommend a smaller, tech-savvy hosting provider that has been around for a long time, who has no tolerance of abuse on their network, who is easy to communicate with directly (no paying for 'Business Support' just to talk to a clueful person), and ideally who mostly rents dedicated servers / colo rather than cheap virtual servers.