Given how poorly the USPTO has performed thus far, it seems impossible that this could be correctly implemented. Better to err on the side of openness, and abolish them altogether.
But there are also some pretty deep stuff that seems less obvious, my favourite example is MP3. I'm no expert in the field, but it does not seem at all obvious to me to compress music like that, and it seems to be the result of a real invention process.
It's clearly in everybody's interest that they publish their codec as widely as possible, rather than make a broke-by-design binary-only distribution. Why should they not be allowed the same protection as, say, Volkswagen inventing a new fuel pump?
However, there are a lot of very smart people who invent formats and don't patent them. For instance the JPEG format is clever in a very similar way to the MP3 format. In this instance the format was created by companies with an interest in a great format for their devices - cameras for example.
MP3 (well, a lossy music codec of some kind) could have been created by a similar group trying to make music players interoperable. It might have even been created by open-source advocates. Think Ogg-Vorbis, for instance.
I don't think that we'd live in a world with less cool formats if patents were abolished (yay!). If a format is required to solve a problem, it will be created. Open protocols without patents should be encouraged.
Theoretically, it's possible, but in theory communism would work if everyone just did their best to make it work. Reality is different.
There are obvious and simple ways the patent system could be improved. For example, drug patents already are treated specially, in that they expire quickly--perhaps a similar system could be applied to software patents. Or, exemptions could be made for implementations of patented software that exist for reasons of interoperability or compatibility. Another option would be to enshrine into law the promises companies make not to sue. (As in, the company is not allowed to renege on their covenant not to sue--this is actually probably not really possible from a legal standpoint, but I'm not an expert.)