In most instances, you get what you pay for. I handle IP reputation by colocating with good, if somewhat conservative, colo providers. The most recent colo provider contacted me after placing my order to ask what services I intended to run, to match my provided address with WHOIS on the main domain I planned to use, and to ask me to explain the discrepancy between the IP from which I filled out their web form and my given address. Some people would be indignant about this. I certainly was not. I'd rather ALL people have to jump through many stupid hoops, myself included, than have a network where money is the only prerequisite to joining. That provider, if anyone is looking, is Turnkey Internet. They're definitely worth considering if you want to deal with real people.

Once you have an address (or a new-to-you address), you have to break it in, so to speak. I did this by setting up reverse DNS (of course) which unambiguously matches the hostname, the primary IP, and the HELO / EHLO name given by the server. I then set up SMTP-auth so I could use it for little bits of email here and there. I did this for several weeks before I started increasing the volume. At the same time, I configured a long running server elsewhere to allow relaying from this machine and started sending email list traffic through the new server, which relayed through the long running server so that services like Google, Yahoo, Hotmail and others would get more exposure to the new server, albeit indirectly.

I also took the time to proactively register the new server and IPs with anti-spam sites and blocklists. This usually involves providing proof that the contact information is real and works, but it helps lots.

Barracuda gave problems - they listed my new IPs even after requesting delisting TWICE, but an email that got to a human fixed this more permanently. While frustrating at first, the fact that you can correspond with a human is always a good thing.

After more than a month of this, I started sending directly from this new server. As anyone who has done it can tell you, running a mailman list these days is hardly trivial considering how quick most services are to consider mail lists spam. But regardless of how much time it takes, it's worth it to take the time, to be careful and deliberate. I've only had to do this four times in the last decade, but not rushing is always worth the extra energy.

Of course, VPS IPs are often much more "beat up" and are usually considered undesirable neighborhoods, more so than colo networks. That's partly due to the more transient nature of VPSes. When you colocate, you're more invested, generally speaking, so you're more apt to keep the IP for many years.