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