I don't know if it's feasible, but I would say that they should be much more selective in what kind of patents are granted, both ruling out the more frivolous patents, and also trying harder to confirm that there's no prior art (perhaps through peer review as in science). The costs for this should be for the applicant of the patent.