When a suit is filed, an engineer is given the problem and told to build clean-room implementations. If he gets it in under a month, it's obvious and overturned. If he gets it in a day, it's extremely obvious and the plaintiff is fined three times the asking damages. If he gets it in under an hour, thirty times.
This disincentivizes completely bogus patent claims, and should bring the total rate down to something manageable.
When the proposal is submitted, the engineer attempts the recreation. If he fails, the patent office pays him. If he succeeds, the attempted patenter pays for a month of his salary. If he succeeds in under a day, the patenter pays a year.
This gets up-front examination, but weakens the incentive to hire good engineers and doesn't guarantee to make trolling unprofitable.
Once something is patented, the idea is out there for others to hear about (not just because they can read the patent; the original inventors can now talk about it, too). And ideas that get out into the wild tend to spread.
On the other hand, after all these years of having patents on obvious things granted, it might be no bad thing to try throwing out some genuinely inventive patents instead for a change :-).
(My own preference: either do away with software patents completely, or substantially shorten their term. [EDITED to add: the latter probably only makes sense if you can greatly reduce the latency between initial filing and granting. Which would be a good thing anyway, for all patents.])