Whenever HN discusses self-hosting email, half the people with self-hosting experience say they never had any issues and the other half says they had so many issues they had to give it up.

I self-hosted for years and I did all the standard things you're supposed to do, but I had tremendous problems with Gmail and Outlook. Other providers usually went through without issue.

I guess there is a certain amount of luck in this, probably related to the provider, or the range that your IP reside into. (I guess google and microsoft keep their own blacklists, regardless of what public blacklists say). I wonder if the best course of action in that case is to just spin up a new server on a different provider and try again.

FWIW, in my case, I am running the server on Hetzner, even though is supposed to have a bad reputation, but I have been using its IP for more than 10 years for other things (web server, personal services etc) so I guess that helps

How much of this is just down to your mail server being randomly assigned an IP address with dubious history or not?