I've been running a mirrored pair of virtualized SurgeMail servers (for my personal stuff) for over a year now. I'll mirror what ChrisP said and share a couple of things I've learned while setting that up....

Originally when I decided to setup a new pair of servers-- I set out to have the servers on two different cloud providers.  I wanted to stay away from the "$5 unlimited everything" fly-by-night operations you'll find posting on various low-end hosting forums.  

I discovered finding two "compatible" providers for hosting a mail server proved to be harder than I thought....

-Many of the "big boys" generally have non-negotiable outbound SMTP/Port 25 filters in place.  Some of them (*cough* Digital Ocean *cough*) only filter port 25 on IPv6.  Their explanation for this? Because most blacklisting happens at the /64 level, and they don't give their users a full /64.  (Why? I'm not sure. Any best practice document you read will say the minimum allocation should always be /64, and any decent virtual hosting provider will give you this without any questions asked).

-If you do manage to get a server up and running on something like Amazon Web Services-- you'll usually find the reputation of the public IPv4 or netblock you're using is so trashed (i.e. blacklists) by previous users that it's unusable to send mail out reliably.

-Some providers that block port 25 suggest having you relay all your mail through their own SMTP relay service  (Which has it's own set of issues because these services usually allow things like bulk mailings and will frequently get flagged by spam filters).  I don't like this approach, myself.  At this point, I'm asking myself why I'm running my own server if I have no control over my outbound email's destiny. :)

-I've mentioned IPv6 a few times-- that was another one of my "requirements". (Which is another reason why many of the big hosting providers don't make the cut).  The current release of SurgeMail handles IPv6 reasonably well (if you enable it) so there's no reason not to insist on IPv6 being mandatory when picking your host.

~Matthew