At least Vultr and Linode will also communicate with other big providers (e.g. Gmail or Outlook.com) in case you have delivery issues due to history of the IP addressor subnet before you took it over.
However, i'd say that it's less of a matter of choosing a VPS host and more one of making sure that the IP addresses that you get are not in any blacklists. This seems like a good starting point for those sorts of checks: https://dnschecker.org/ip-blacklist-checker.php Or maybe this: https://mxtoolbox.com/blacklists.aspx
I think the actual question would be: "Which VPS hosts have the least blacklisted IP addresses for hosting mail servers?" But i'm afraid that i cannot answer that one, because after a brief search i could not find any articles, which would check the IP blocks owned by different hosts and what percentage of them are in blacklists, which would probably be a large undertaking.
Until then, most of the answers will probably be subjective, along the lines of: "I use $HOST without many problems." (like my answer above, though even then someone could get a blacklisted IP address and their answer would be the exact opposite to mine).
I've not had problems with Hetzner and Scaleway. Before that I used to host email on random vendors I saw on Low End Box[1] and never had problems.
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.