People like to hear that DNSBLs are a problem. And then they like to repeat the accusations. Not sure how folks have gotten attached to the idea, but I'm certain it's not from detailed investigation.
For one thing, don't conflate the mechanism with the implementations. Anyone can publish a DNSBL. You could. And you could make your list all false positives. It would be a bad idea for people to subscribe to your list. Caveat emptor, right?
And that's why you get false positives. You've chosen badly. And you're not using the lists for scoring — sounds like you're using them as final arbiters.
The "trick" to getting DNSBLs to work is to choose wisely. You have to do some research into how the lists are made, and since it's you who will be blocking emails based on the information provided by the lists, it's your responsibility to understand the nature of that information. What are the listing/delisting policies? If you don't know, you're not being a smart consumer. "... everytime some angry recipient with a vengeace decided to file a spam-report ..." Hopefully you know better than to think that every DNSBL is made this way.
And the "smart" spam filters, so you know, are resource intensive. Instead, it's possible to eliminate lots of spam using extremely low resource checks. Validating the SMTP "HELO" (requiring they give FQDN, non-bare address literals, not your domain or IP, and a couple other checks as per RFC) will nix half of spam off the bat. And you can eliminate another third of spam (two-thirds the spam passing HELO checks) by using (well-chosen) DNSBLs. DNS lookups are cheap (and you can download zone files of you're worried about outages). That's 83% of spam cheaply nixed, all before you even get to "MAIL FROM:". If your "smart" checks are building Markov chains and feeding a naive Bayes classifier, that's gonna take time and effort in processing power, in disk resource, in procedures and staff attention/knowledge for maintenance.
DNSBLs are clearly a way to fight spam. But you have to know what they are and how to use them.
Shopping for DNSBLs takes effort, it's true. If you want to do a good job. Once upon a time, Al Iverson's http://www.dnsbl.info/ was up-to-date and gave wonderful statistics on success rates of the various lists (using his (rather knowledgeable) measures). Doing the research now without such a resource is much more challenging.
I use Spamhaus's XBL and SpamCop's SCBL. That's it. Combined, those give me the aforementioned inexpensive 33% spam reduction. (If I used them before the HELO checks the reduction would probably be near 75%, my guess.) I vetted the lists for efficacy (true positives v. false positives), policy (how they're made, listing and delisting), and longevity/reputability. I've been using these guys for 5 years without a hiccup.