Any provider with a very cheap or free cloud tier is gonna be blacklisted somewhere; it can be hard to get an IP that doesn't appear (spin one up and test some blacklist checkers to see).
Vultr allows you to bring your own IP space and do BGP peering. Then any work you do to increase the reputation of the IP space will be portable across providers.
It can take months to spin up an IP correctly.