The solution is to attack those two problems. Not to attack the concept of patents themselves nor NPEs.
If the anti-patent-troll efforts were focused upon those two points specifically, meaningful reform would be much easier to achieve; fewer special interests would be aligned against the changes.
This is all exacerbated by the fact that the patent agency is a government agency, where there really isn't anything incentivizing them to get better. And yet on the other side you have lawyers who are 100% incentivized to create the most convoluted patents to actively confuse (the already ill-equipped) patent clerks and juries.
I also agree with the statement "if we could just grant the right patents then this wouldn't be a problem". I just don't see any reasonable way to increase the fidelity of patent grants, nor a reasonable fallback system for when a bad patent DOES inevitably get granted (trial by jury for discerning innovation is probably the worst method).
1000 years ago you could be a mathematician, poet, and biologist. Today, you have to go to school for 5 years to get a PhD in an incredibly focused subfield. 100 years ago the patents you were dealing with were "machine that makes light". Now its methods of improving graphics performance when running on this super specific kind of computer architecture. It might have been reasonable for an outsider to make a judgement call before, but I seriously don't think it is anymore.
It's such an extremely absurd idea that I'm amazed at how many people accept it as being normal. Patents are the closest thing we have to literal buying of laws.
But it's not my impression that the patents that have been causing a lot of trouble are largely of this extremely specialized kind. A lot of them seem to have to do with implementations or applications of networking -- like the one Newegg is currently defending against, which is claimed to cover SSL/TLS key negotiation. There was another a while back that purportedly covered podcasting. I don't think it takes years of study to understand what these things are.
As an aside, I think that the funds should come from the patent applicants themselves, and should cover the level of examination required. If examination is insufficiently deep, then the depth should be increased and the fees increased to cover the cost for this.
IME, patent office fees are tiny compared to the amount that applicants generally spend on their patent attorneys, so there should be no hardship there.
Patent application fees should reflect the real cost of processing the application. If improving patent quality requires an increased processing cost, then this should happen, since not doing so unreasonably increases future litigation costs for everyone. Subsidizing small companies' applications might then be reasonable if we want to promote startups and smaller research groups, but there's no reason to subsidize the largest companies' applications.
Furthermore, if you aren't against patents in general, there is no principled argument that can be made against software patents in particular. Software is just as inventive as other realms.