Now that the EU parliament has stopped the legislation on software patents, it seems time to summarize what we have learned:
The whole problem arises because it is much easier to copy information than to produce it by other means. On the other hand, what's great about information is that you still have it if you give it to somebody else (this is the idea behind open source).
So, there are patents in the first place because you do not want to disfavour companies that do expensive research and development to companies that just save these costs by copying the results of this R&D. The state provides patent facilities because R&D is in it's interest.
The owner of the patent on the other hand should not use it to block progress and competition in the field. He should therefore sell licenses to the patent that reflect the R&D costs. Otherwise patent law would promote large companies and monopolies as these are more likely to be able to afford the costs of the administrative overhead of filing a patent.
Therefore in an ideal world the patent holder should be forced to sell licenses for a fair price that is at most some specific fraction of the realistic costs of the R&D that lead to the patent (and not the commercial value of the products derived from the patent). Furthermore, the fraction could geometrically depend on the number of licenses sold so far such that the 100th license to an idea is cheaper than the first and so on (with the idea that from license fees you could at most asymptotically gain a fixed multiple of your R&D investment).
This system would still promote R&D while stopping companies from exploiting their patents. Furthermore it would prevent trivial patents as those require hardly any R&D and are therefore cheap (probably, you should not be able to patent an idea for which the R&D costs were not significantly higher than the administrative costs of obtaining the patent).
Unfortunately, in the real world it is hard to measure the costs of R&D that a necessary to come up with a certain idea.