I use Hetzner, personally.

Did a bit of a cost analysis here: https://figbert.com/posts/moving-to-hetzner-from-digitalocea...

Some parts of Hetzner IP space are in blacklists. It is a bit of a lottery here. Be sure to check IP you got.

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).

Vultr, Linode, Njalla, Hetzner, Scaleway

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.

I’m hosting my email on Scaleway for 4-5 years and have no issues with deliverability. Last time I checked my email server was correctly configured.

I'm hosting on linode, and once I had my SPF & DKIM records setup, things went a lot smoother.

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.