It's pretty much out of your control. If the server you rented has a tainted IP reputation, you're done for. Instead of cycling through to get the good IP, which isn't too easy to tell, you should just use a proxy service.
If you're on a small scale, those 2 services I mentioned aren't going to cost you much (free and maybe about 5 cents a month.)
I even proxy my hobby personal domain server because I don't want my personal mails get buried in people's junk folder.
