Look into some kind office internet ISP, who offers static IP-s. At least my experience with those is good. You probably need to make exception in Spamhaus PBL list ( end-user IP address ranges), I haven't seen any problems after removal. If that isn't possible, go with some solid colocation (old school company, who don't offer cloud services).
