Did Microsoft's excuse check out, though?
Google "caught" MS stealing results by manually adding an unlinked page with a unique nonsense string on it into their index. Then they installed the Bing toolbar, searched for the string in Google, and clicked on the only result. Soon after, the same result showed up in Bing.
Google claimed that Bing must have "stolen" the search result because it's not linked from any other page, so there was no organic way for Bing to find it. But it seems pretty normal to me.
This assertion appears to be supported only by your use of scare-quotes around "caught." Is there any further detail you can supply as to why Google's charge should be treated with skepticism? How else would the page have gotten into Bing?