I have no problem with any patents assuming they are truly innovative. The biggest problem with patents is that the non-obviousness step is almost ignored from my experience.
What they need is a way to determine whether an invention is an obvious extension or not. I suggest they do this probabilistically. Let's say it's a non-obvious idea if only 1/100 skilled practitioners would come up with it given the generic problem statement. Then it's easy to test. This would increase the cost of patents (a good thing imho) and dramatically decrease the number of spurious patents.
The interesting thing would be what proportion of inventions would qualify under this scheme. I have a feeling very few.
In ordinary language (though perhaps not in law), "truly innovative" is not the opposite "obvious". I believe the language involved in US patent law is "the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains." So in my non-legal opinion, the standard is two low on it's face, whether or not it's enforced. I wouldn't consider a solution obvious if it took me even an hour of brainstorming, but IMO that shouldn't typically warrant a patent.
Regarding your proposed test for patentability, I've thought about similar tests before. There would be many practical difficulties, like deciding who frames the problem. Some of the most innovative inventions are just properly identifying a poorly understood problem. But I think something along these lines is the right way to go.
Another possible variant would be to force licensing of the patent for an amount proportional to the expected cost of developing the solution from scratch, maybe weighted by the potential market.
The biggest problem with software patents is a limited solution space. For a poor example, implementing text rendering on a graphics card is something which you can very easily formulate three attempts and measure which one works best against common criteria (sharpness, speed, etc). Once the best solution is patented, it's very unlikely anyone else will be able to use this technology (particularly in situations where the patent is a small part of a larger package, say, an operating system) and they will be forced to settle into the second best-fitting solution.
You know, an even better method might be for the problem statement to be open to the public. People could then submit their solutions, and if no one came up with the same idea then it's patentable.
This way if it truly is something with a massive inventive step, then people can get the patent. If it's something as simple as what you describe, then there's no way it would be patented in the first place.
What they need is a way to determine whether an invention is an obvious extension or not. I suggest they do this probabilistically. Let's say it's a non-obvious idea if only 1/100 skilled practitioners would come up with it given the generic problem statement. Then it's easy to test. This would increase the cost of patents (a good thing imho) and dramatically decrease the number of spurious patents.
The interesting thing would be what proportion of inventions would qualify under this scheme. I have a feeling very few.