If you actually control the DNS, you can set up SPF records without much difficulty - basically all they'll say is "IP address 1.2.3.4 is an authorized source for email from this domain." Unless the host controls the DNS, SPF records aren't under the control of the host. In fact, even if you move the email elsewhere (e.g. to Office365 hosted Exchange) you will probably still want to set up SPF records.
However, that probably won't make much difference to your current situation. If it's a shared web host and they're running email on the same box then all that needs to happen to get blacklisted is for one or two other accounts on that same hosting box to be compromised and start sending spam. That could be a website compromise or it could be a compromised email account - all that will matter is that it's traffic coming from that IP.
Running an email server in-house is also an option, but it's not really one I'd recommend unless it's a pretty good-sized client where the per-user cost of O365 or other hosted Exchange would start to approach the cost of installing, updating, maintaining, etc. an in-office server. There are ways to do it less expensively with open-source options like Kolab or third-party options like MDaemon, but when you add up the extra labor and the potential drawbacks it starts to look like "OK, we can save you $200/month by dropping Exchange, but it'll be harder to connect phones to your email, you may have some delivery problems, and you may not have things like shared calendars, etc. unless you're using the webmail interface."
Oh, and self-hosted means they'd have to have a static IP, get reverse DNS (PTR records) configured for it with the carrier, and get that IP removed from the blocklists that simply aggregate all of the IP ranges allocated by carriers to clients (e.g. one of the SORBS lists).
If you're using something like Spamhero for spam filtering, you may also be able to use them as an outbound "smarthost" or set up your email clients to go out through them. This may require an additional fee on top of your regular subscription.