I propose a different solution. If I may briefly quote Wikipedia (from http://en.wikipedia.org/wiki/Inventive_step_and_non-obviousn...):

The factors a court will look at when determining obviousness in the United States were outlined by the Supreme Court in Graham et al. v. John Deere Co. of Kansas City et al., 383 U.S. 1 (1966) and are commonly referred to as the "Graham factors". The court held that obviousness should be determined by looking at

1. the scope and content of the prior art;
2. the level of ordinary skill in the art;
3. the differences between the claimed invention and the prior art; and
4. objective evidence of nonobviousness.

In addition, the court outlined examples of factors that show "objective evidence of nonobviousness". They are:

1. commercial success;
2. long-felt but unsolved needs; and
3. failure of others

I think software patents pose several problems for the Graham factors:

(1) Prior art is too hard to locate. The generativity of software is so great; it is so easy to invent new things; and so many things were invented before anyone even started patenting many of them, that it is very difficult to be confident that one has found all the prior art relevant to a particular patent application.

(2) The field is vast and continues to grow, with many subfields. No one person can know everything that has been done in software. This renders the very notion of "ordinary skill in the art" problematic.

(3) Because of those two factors, assessing the differences between the prior art and the claimed invention -- which was always a subjective process anyway -- becomes intractable. Anyone can line up experts to say that the invention is or is not obvious.

Thus, the only one of the Graham factors that is workable for software patents is #4: objective evidence of non-obviousness. I suggest that to obtain or prosecute a software patent, one should have to show objective evidence in at least one of the three categories in the second list quoted above. Such evidence could take many forms. The best, perhaps, would be multiple published academic papers showing an attempt to solve the same problem and presenting clearly inferior solutions. Another kind of evidence might be reviews of products complaining of the problem that the invention purports to solve.

Commercial success is in some ways the best metric and in other ways the worst. The biggest problem with it is that one has to file the patent application before releasing the product; at this point, evidence of commercial success is obviously unavailable. Another problem is that there are, of course, other factors that play into it ("execution" as they say) and that are often even more important than one's technology. Still, if one manages to build a business around an invention where others have tried and failed to do so, I think that has to count for something.

I believe that requiring objective evidence of non-obviousness would solve, or go a long way toward solving, the software patent quagmire because in my opinion, the majority of software patents these days result from the application of relatively well-known techniques to novel problems. That is, it's usually the problem that's new, not the solution; once one has noticed the existence of the problem, the solution is not hard to come by. Obviously, for a novel problem, there is not going to have been time for anyone else to attempt to solve it and fail, leaving behind some public record of their attempt.

Although IANAL, it also seems to me that the change I'm proposing is incremental enough -- close enough to the rules that the Supreme Court has already enunciated -- that it could actually be accomplished.

EDITED to fix formatting, and also to add: I wanted fo get the above posted because I've been thinking about it for a while, but I don't mean to dismiss Lemley's point at all. We clearly need to clamp down on functional claiming as well.