I'm increasingly thinking that a large part of the problem is that the folks at the Patent Office just aren't well enough versed in the software side of things to grasp what's going on with it. So another agency, or perhaps a specialized branch of the Patent Office might be the best way to approach it. I detest bureaucracies as much as the next fellow, but they exist in the first place because sometimes they're the best way to approach things. The drawback, of course, is that you need to constantly stand by with a machete and a flame-thrower to prune them back.
