Oh i guess thats what they meant by blacklist, was not thinking of ip reputation? If that's the issue, I have never experienced it, I believe there are tools you can use to see if your ip is bad and in that case u can probably ask ur isp for a new one (if u pay for static ip).

My other advice for using your own domain still stands, makes it a lot easier to swap around providers.