Prime question.. what do you use to send your emails with? If your hosting provider is "sending" the emails via their offering.. that can be a major issue if you are on a shared environment as YOUR reputation is as good as the worst client they have on the same system. So if your hosting provider has had a lot of spammers (or folks reported as spammers) sending mail through their "it's offered free in your hosting package" email solution.... you are going to have problems.
If you are hosting on someone like Digital Ocean, Linode or such (low end VPS offerings) and "rolling your own email", their IP's are frequently on block lists because of the same reason.. it is easy and cheap for spammers to spin up a quick VPS, do a month or two of blasting spam, get the IP blocked and then go and spin up another VPS and rinse & repeat. The damage to those "old" IP's remain, and the hosting provider isn't going to go through the hassle of getting them cleaned up.
That's why, for reliability, most use outside providers that strictly deal with email delivery (I use Amazon SES and even with it, they have an IP on at least one spam list).
