My personal opinion - for what that's worth - is that this kind of scenario comes pretty close to representing what would happen if there were no patents in software (or any other field for that matter). Innovation would still happen, and would probably happen
even faster than it does now, because of the "arms race" effect. Simply put, a firm would be forced to innovate constantly, quickly and fiercely, to stay in front of its competitors.
Combined with the fact that I am appalled by the idea of use of government force to block someone from using an invention - that they may have arrived at independently - just because someone else patented it first; and my belief that there are too many smart people in the world for any really useful idea to stay undiscovered long, I advocate for simply abolishing the entire patent system.