Our domains, which reside in a shared hosting service, are constantly appearing in blacklists like this one: http://cbl.abuseat.org/

This results in emails being blocked and lost. We have notified our hosting provider, they have (supposedly) taken extra measures and have done several unblock requests. Only to return back to blocked a few hours or days later. They finally gave up and told us that this is a common problem with shared hosting. Apparently, some forms of mass email can be perceived as spam by these blocklists, so they end up blocking the whole server. Our only real solution is to move to dedicated hosting or VPS, and have our own unique IP.

Question... is this normal indeed? Is our provider being truthful, or simply incompetent to deal with the real problem?

Thank you