I run my own mail servers on linode and vultr as long as they have existed. Prior to that I had dedicated servers. For a while, I relayed my forum emails through my mail server and it was very rare to be flagged as spam and I never received a bounce or back-scatter.

YMMV depending on who had your IP address previously. If you get a bad (previously blacklisted) IP, then you can always spin up a new VM.

Some of the really low-end VPS providers are so relaxed they get their AS number blacklisted in uceprotect.