Isn't it the case that you get a year's grace between coming up with something and filing the patent?

Microsoft would have to document that they had the invention the full year before they filed the patent. Also, this was the middle of the dot-com boom. It's easy to find prior art from the filing date. It would take some effort to find prior art from earlier than that, but I'll bet it's out there, somewhere. Of course, cookies were part of the original Netscape 1.0 in 1994. The design clearly anticipated shopping sites (you see it mentioned all over the place in early documentation, to help track your shopping cart, etc.), which might partially invalidate the patents all by itself.

Also, I seem to recall that the one year grace period only applies in U.S. patent law (everywhere else it's "first to file"). Microsoft probably filed this internationally, so they may well have rushed the patent out the door.