I've been on digital ocean for maybe ten years but I now want a place where I can run a mail server. That rules out digital ocean because thei IP address blocks are on too many blacklists. I'd be curious to hear other suggestions (but not aws, whose pricing model is too complex).
Look into some kind office internet ISP, who offers static IP-s. At least my experience with those is good. You probably need to make exception in Spamhaus PBL list ( end-user IP address ranges), I haven't seen any problems after removal. If that isn't possible, go with some solid colocation (old school company, who don't offer cloud services).
