IMO, any low-cost VPS provider is going to have a poor reputation. I've even had trouble running websites on some of them, as some "endpoint security" products have their IP addresses blacklisted, causing users to get alarming warnings if they try to visit sites hosted there.

You'll run into the same issues with the "free/trial" tiers of bulk email services like Mailgun.

I agree with OP, you pretty much have to at least send your outgoing email via an established, widely-accepted SMTP service provider, or in some other way pay a lot for a "clean" reputation.