Maybe it helps to host the email server in a less known and maybe a bit more expensive ISP. I have been self hosting my company's emails for 10+ years and even changed IPs halfway (VPS migration). I vaguely remember having to setup DKIM and such when that became a things and never got any deliverability problems since (fingers crossed).
Have you actually hosted an email server on all five of those? As you mentioned in your other comment, it can be very helpful if your VPS provider is able to respond to support requests asking Microsoft for IP addresses to be whitelisted. I can't imagine all VPS providers would be so helpful but you didn't mention which one you were using in that comment.
Late to the game. Vultr does block port 25 by default, but if you request it to be unblocked for your account and agree not to be abusive with the protocol, they'll open it up for you.
Don't know about others, but Linode and Hetzner have parts of their IP space on spamming blacklists. As does Digital Ocean. So it's a lottery, basically.
