I'd say Microsoft started going downhill after 2002, when they disbanded the IE team and embarked on the disaster that was Vista. But I remember that when I started college in 2001, I hated Microsoft and yet virtually all the software on my computer was by them. It's a sign of market dominance when your customers hate you and yet use your products anyway. ;-)
Eh. We also got WindowsME in 2000, which was arguably the worst version ever. And to be fair, Office has been mostly re-arranging the furniture and re-painting the walls since Office95. And...let's not forget Bob. Bob was Microsoft's Buzz, circa 1995.
That said, sure, it's not like MS got to their current state on January 1, 1996. And there's no way I'd argue that they (or Google) are going away soon. My point is only that Google is starting to show signs of lumbering corporate giant-hood, and that it has happened pretty quickly, in comparison to MS.
And Win7 is miles ahead of XP, although XP is better than Vista.
There's still time for that not to happen, but all the signs are pointing that way.
But the recent, high-profile launch disasters, the clutter that's slowly creeping into the result pages, and stuff like the search page background goofiness...they sure feel like early MS-style mistakes.....