To compete with Google on search you have to do to Google what Google did to AltaVista: be noticeably better, consistently. As you said, Google is nowhere near good enough yet.
So this is what Google is scared of, and that's why it's in their best interest to keep innovating, because otherwise someone somewhere might beat them to the next real breakthrough.
Bing so far has failed by not making any real technical progress, and only reaching parity. That means right now they have to compete on brand, and that sucks for them.