DO's equivalent Elastic IP product can't be used to originate email, unfortunately. They actively block it, and it's against their ToS (Last time I looked). Otherwise I would have preferred to host it there. If you allocate a Droplet, groom it's IP, and then terminate it (either for yours or their reasons), they only "promise" to give you back the same IP, and I'd hate to have to setup a new IP in a rush.
Before I setup my DO I asked them can I set up ESP? They said absolutely. AFAIK they only ban constant abusers. I sent to very clean and engaged list (noone above 45 days of inactivity) and hadn't had any problems. I have "emergency setup" on different hosting but you are right on point it would take month to come back to same mailing levels.
DO TOS doesn't say you can't send emails. Their control panel allows you to setup rDNS yourself BTW.
These days largest ESPs (Google, Yahoo/Rocketmail, AOL/Live/Outlook/Hotmail, GMX, Wanddo, Orange, UOl, BOL) only really look at IP in 4 categories: narrow whitelist (other biggest mailers, private contracts [banks mostly]), wide whitelist (static IPs of all sort including your $5 DO), greylist (home IPs, mobile IPs, all other IPs that probably should be mailout out in the first place), blacklist (in terms of you land there forever - don't confuse with having your IP blacklisted). Long gone times when ESPs tried to figure on some scale 1-100 how good your IP is.
About your mailservers: location doesn't matter, as reputation is being build over the time. I have Digital Ocean $5/1GB machine that was previously used for heavy spamming (had to submit tickets with all biggest SpamHouses) and since then has pristine reputation with constant 97-99 SpamScore, etc. You just need about 45 days of constant raising volume of mailouts and you be fine. This machine currently does about 40,000 mailouts a day.