From what I can see, Microsoft put little or no effort into invalidating the patent on such grounds. Instead, they concentrated on one argument: that the inventors listed on the patent had written and sold a product ("S4") more than a year prior to filing for the patent, that Microsoft claimed may have implemented it -- but its source code is long gone, so they had little (if any) evidence of its having done so.
The inventors both testified that it didn't; Microsoft's counterclaim was that since S4 was never presented to the Patent and Trademark Office, the burden of proof to show that it implemented the patent was reduced from the "clear and convincing" level normally applied to invalidating a patent to the "preponderance of the evidence" (aka "51%") level applied to most situations in civil cases.
When all was said and done, all the Supreme Court did was upheld what they'd been saying for roughly a century: that though the wording has varied slightly (e.g., "clear and cogent" vs. "clear and convincing"), that if you want to get an issued patent declared invalid, you need to provide considerably stronger evidence than for most other situations in civil cases (though still less than the "beyond a reasonable doubt" level that applies to most criminal cases).
At least to me, it looks like Microsoft decided to do a bit of "long shot" gambling, taking the chance of losing the case in the hope of doing a bit of common-law reform of the patent system that (if they'd won) would have made it much easier to invalidate patents.
If they'd presented clear evidence of prior art that invalidated the patent, that would have won this case, but deprived them of the chance at changing patent law in general.
