The best solution I've been able to find is to self-host /almost/ everything, but route outgoing mail through Amazon SES.
The pricing for vanity email volumes is negligible (a few cents a year), and they have people whose full time job is wrangling IP reputation / Office 365 / etc.
This setup has survived several ISP/hosting switches; at times when I am lucky with IP reputation I route only mail going to Office 365 recipients via SES and deliver the rest directly; at times when I am less lucky, everything goes via SES.