I've been a moderator on Stack Exchange for a few years and have watched flag-handling evolve there. Here's what I've learned from that so far.
Once upon a time, SE had a flag ban -- if too many rejected flags piled up, you couldn't flag any more. (This was visible to the user, not a shadow-ban.) That stopped the bleeding but wasn't recoverable; once you hit the ban, you were done unless an employee manually removed it. A perma-ban does not allow users to learn and improve.
This was replaced with a system of warnings and temporary flag bans. If you have too many recent rejected flags, as a proportion, you get a warning when you start to flag again that says something like "Wait! Your last few flags were rejected; read (some link here) before you proceed". If you continue past that and have more rejected flags, you're blocked from flagging temporarily. Rolling evaluations, warnings before bans, and temporarily bans help stop the bad flags without locking people out forever.
An SE user can see his flagging history -- what he flagged and whether the flags were accepted or declined. SE also, along the way, added more-detailed flag feedback. Instead of just accepting or declining a flag, a moderator can choose a standard response from a list or type a custom response. Many (most?) users who flag incorrectly are doing it out of ignorance, not malice. Feedback on individual flags can help educate users so they're more likely to flag correctly in the future. Users do need to see the feedback, of course, and some have raised the visibility of this feedback as an issue on SE.
Finally, there is a limit (per day) on how many flags an individual user can raise, and it is tied to the user's track record. Better flaggers get more flags, but everybody hits a cap eventually. (I think it's something like 100/day on SE.) Users can see what the limit is. Knowing that there is a limit might encourage users to use their flags more carefully (or might not; not everyone pays attention to such things). You say you are concerned with losing the positive flags, but if your community is at all active, somebody else will flag it. Joe Flags-A-Lot doesn't need to be able to; your mods will still find out. Individual limits contain prolific flaggers without hindering other users, and you can set the limit based on individual records.
Your question suggests a preference for false positives over false negatives; you'd rather get junk flags to avoid missing the real ones. But your moderators are getting frustrated with the workload. It sounds like it's time for you to consider allowing some flag-worthy stuff to live just a little bit longer, to allow your moderators to see a better hit rate. Plus, as I said, these are all individual limits, designed to slow down users with bad records; the rest of your community can still flag. (Are you, perhaps, over-relying on a few active flaggers? Is it time to get more of your community involved in this activity?)