You will need to look at the hosting terms and conditions for any provider you are considering. Some have very strict policies regarding ANY email marketing, regardless of legitimacy. The other thing you need to look at is the reputation of the IP block they issue you. A previous customer could have sullied the reputation of the IP block you get. If any of the IPs have been blacklisted by other ISPs, SpamHaus, SpamCop, etc. you will have a tough time getting any email delivered.
And don't forget your domain registrar. They have terms and conditions that can impact you as well.
Are you using your own mail server? If so, make sure you have proper reverse DNS set up. DKIM and SPF can be helpful. Make sure you have a working opt-out system, a double opt-in process is better. And make sure you are mailing to your own, first generation data. If you can't prove site specific opt-in by a user to your site, you will never win a spam dispute with your hosting provider, domain name registrar, or anyone else.
It is getting more and more difficult to do any email marketing these days. Even if you follow all the rules, you will run into complaints and shutdown threats.
You may want to consider using an email service provider to do the actually mailing. They can provide the server, IP, manage feedback loops, etc. For a price.