We are running our mail servers on VPS. And frequently get listed in a spam black list. So that our clients began to complain about mail sending failures. (mails are rejected by the recipients). The reason to be listed in the black lists is that, some guys running VPS of the same provider sending spams. Searched the Internet to find another VPS hosting and saw that many other VPS hosting firms have bad reputation and blacklisted. Could someone give me advice on how to get rid of this issue or point me to the solution. Thanks

We are running our mail servers on VPS and frequently get listed in a spam black list. Our clients began to complain about mail sending failures. (Mail is rejected by the recipients.)

The reason to be listed in the black lists is that, some others running VPS on the same provider are sending spam.

I searched the Internet to find another VPS hosting and saw that many other VPS hosting firms have bad reputation and get blacklisted. Is there a workaround for this?