I've just moved my workplace to their own email server. Bear in mind that we send no spam whatsoever, nothing that can even be construed as spam - it's a school.
We have previously exhausted:
1&1 Internet - We host our domains with them, but they are terrible for email, always in the blacklists, they never do anything to resolve it, not enough backup servers or whatever, so your mail ends up being refused by the other end half the time. They operate a "smarthost" that's just useless half the time.
Virgin Media - Despite having a leased line, the number of emails you can send is limited and setting up things like reverse IP so you can run a mailserver is just unnecessary manual and complicated. I gave up. We tried to go out from our Exchange server via this direct and it's no good as most stuff just gets refused or limited.
Our VDSL ISP (unnamed because they are helpful) - no good because that's only a backup line for us and shouldn't be our primary outgoing. Also their SMTP smarthost occasionally ends up on a blocklist. and is only contactable over their connection (not our leased line).
In the end, I purchased a dedicated server with a datacentre host and we just relay all our email through it - incoming and outgoing. It lets me greylist, filter, anti-spam before it ends up on our local network, but then just passes email through to our Exchange server. Outgoing server is "always up", we control our own reverse DNS, SPF, DKIM, etc., it's only our own fault if it's ever blacklisted (hint: It's not), can store-and-forward on our policy rather than some random host's, and keeps the performance hit of the hundreds of thousands of spam, etc. connections off the local network. We're also pretty sure that we're talking to the endpoint mail server direct and have TLS where it's possible, rather than relying on some third-party to deliver our mail.
And the backup if that goes wrong is to fall back to some of the above.
But sending email reliably is unnecessarily complicated and in desperate need of a redesign. I still see people's mailservers who don't understand simple things like "try-again-later" responses and drop email.