Oy. I worked at Microsoft for about 8 years (1 year of that was coming back as a contractor after leaving a permanent position). During that time I went through several interviews (got 3 of the positions, didn't get 3).
Interviews at Microsoft are tough, in part, I think, because interviewers know that they have such a reputation to uphold. No, really!
If I had any advice to offer, it would be this: know your stuff, and think out loud. Sometimes I've felt that I bombed an interview because I didn't solve the problem as efficiently as I could have, but it turns out that the interviewer really liked how I thought. Also sometimes I've really aced the interview, but maybe the interviewer was having a bad day or something...
Don't get cocky! Most of the technical people at Microsoft, contrary to the BS in the media, are very, very, very smart, technically literate people. They will be able to smell BS a mile away. If you don't know something, say you don't know it and ask questions about it -- that shows that, even while your present knowledge is limited, you can learn (that's far more important in some people's eyes than just an encyclopedic recall of algorithms you learned in your CS101 class!)
Finally, don't neglect your people skills. We coders can be an arrogant, surly lot. You can't be this way with the interviewer; remember that they're contemplating working with you full time. You have to be upbeat and friendly, even if you don't feel that way.
Good luck, all.
PS: A job at MS is no longer the best thing going. The stock is pretty much worthless these days and the benefits, while still good, are hardly the best in the industry. The pay is decent but not stunning (by moving from permanent to contractor, my net pay jumped over 25%), and they will ask you to work CRAZY hours. Many Seattle-area people have learned how much MS will burn you out and won't work there. I'm not trying to MS-bash (I'm one of their biggest defenders), just warning you in advance: there are better jobs.