[exratione]

Run it in AWS. They keep their IP ranges comparatively clean.

Other hosting services, yes, you may as well not bother. I haven't found another one yet that is reliable enough at keeping deliverability from their IP ranges in good enough order.

Also make sure you set up SPF and DKIM right from the outset.

[danieltillett]

I ran into problems with an IP address I had owned for 15 years. Clean IP's will help, but they don't solve the problem completely. The real nightmare are the emails that just go missing - they don't even end up in the spam folder. If you are running some sort of mailing list it doesn't really matter, but if you are sending important transactional emails the it really does.

Apart from SPF and DKIM also make sure you also set your reverse DNS name and also set up DMARC.