Check out the spam-reports for the "nameservers" that show up in the whois as well as for the host itself.
Sometimes you can pick different nameservers for a domain, and get away from a wholesale blacklist without changing hosts. And you want to check this part out if you do change to another service, anyway.
If it is his email that is the issue, then he should certainly report the ISP. They are held more responsible than individuals who "spam" and if they are selling email addies without permission in the contract, he might be able to get money back on whatever he paid them by complaining to a consumer agency, because that is a serious violation in most places.