[walrus01]

small fee VPS are likely to be in IP space that has a 'bad' reputation from other people who have historically done dumb things in the same /24 or /22, etc, even if it looks clean from RBL checking tools, you have no idea what its reputation is for actual delivery to google and office365.

[superkuh]

Nothing you do excepting buying your email service from the same-self megacorps will protect you from the megacorps whim and mistakes (and even then not all the time). As you and others have mentioned, even relatively large companies get blocked.

We have to be the changes we want to see in the world. Maybe don't use the domain/mailserver for life or death services the first few years and just see how it goes.