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?