I've had similar experiences with Spamhaus btw, they decided to nix my upstream provider and when I complained I was told that I should use another ISP because mine wasn't well liked.
"Wasn't well liked" == "complaints had been received that they allowed their customers to send spam."
I agree with spamhaus. This puts pressure on ISPs to police their customers, or else their decent customers will leave. And everyone can choose whether they want to use providers that allow all contact through, or providers that filter out contact from ISPs that don't police their customers.
there's no incentive for companies running mail services to ensure that legitimate mail gets delivered
Well, there's some incentive in that if their customers truly want the mail and aren't receiving it, they'll have to pick a different provider. I purchased a product once to be emailed to me and had to acquire an alternative email address because the seller wouldn't do business with gmail, yahoo, or hotmail addresses. I didn't waste time arguing with him; I just got an email account that would get his mail through.
it cost me money and effort to migrate my service.
That's the price of offering a service. If enough people want it, they will more than make up for the cost of you going with an ISP they consider reputable. If not, the world has no obligation to keep your costs low enough to keep you in business. A much cheaper thing to do would've been to quit offering your service.