I got good results with Hetzner. But it takes some time to set up a server that complies with all of Google requirements. Also, I once inherited a spammy IP address and took me some time to remove it from spam databases.
I think the advantage with Hetzner cloud is that you rent the IP address separately. If you get an IP with a bad reputation you can stop renting it and get a new one.
Edit: I have not actually tried changing the IP, its just an idea. Also, I hope the spammers don't start doing this and spoil it for everyone else.
I do use SPF but I don't use DKIM or DMARC. On the inbound side, I do use greylisting and anti-spam. I don't tend to change my config between releases of debian stable.