My emailserver runs at linode. It delivered fine for some 10 years, then I started getting blackholed (at Microsoft live, hotmail, 365, outlook). This IP does only mail. Server is secure, up to date and has all the DKIM/SPF nonsense.

It's impossible to reach humans that can help. It's impossible to unlist. So I'm now on my third IP, my last one running mail for 4+ years, from Digital Ocean. Only now, occasionally, does an email get through.

I'm almost 100% confident that Microsoft just blanket blackholes or punishes anything from Digital Ocean or Linode.

I share your confidence that lots of providers blanket drop mail from IP ranges owned by cheap VPS providers.

The cost of swtiching IPs within those providers is low, so spammers have already abused that, and made life worse for the rest of us as a result.

Yes, I had a first-hand experience with this. Cheap VPS was blackholed right away at Yahoo and any attempt to unblock it was not successful. It makes sense though.

Then I set up my own bare metal server and put it into a real datacenter serverhousing. I had couple of problems at the beginning and later once a few years later - problems sending to microsoft - but all those were resolved rather quickly via their forms. And I haven't had any deliverability problems since then.

The serverhousing I used is very strict regarding spam reports. I once tried to use the server also for sending newsletters (no spam lists, just emails which explicitly subscribed). Someone reported it as spam once and serverhousing contacted me soon after that they don't tolerate any spam. I explained that it was not spam and that there was unsubscribe link but I decided to not use it for any kind of marketing again. I think specialized services are better for this.

I use Fastmail and Microsoft Outlook sometimes puts mail from Fastmail in the spam folder. It's only Outlook that does this because when it happens, I ask what email server they use. Always outlook.