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.