I've been through an interview just like this for Nortel. They ask questions that you don't quite expect to hear. I did very well at the Nortel one, though, because I was able to talk my way through the problem. That's all they want to figure out during these interviews. They want to see if a) you'll fit in with the team, b) you're able to do the job. The answer to these interview questions are going to make or break you during the interview if you're able to think out loud, and if possible draw what you're thinking on a white board, or something.
I prefer these "interview 2.0"s over other interviews because I think they're more my style. I'm much better at mapping my way to a conclusion than I am at coming up with algorithms on the spot.
Being able to code an algorithm, or whatever you're both stressing, isn't necesarilly of high importance during an interview if you can convey the theory behind the algorithm, or just explain what it'd do. Psuedocode is typically fine during these, and from the people I've spoken to that recently interviewed have told me that that's the case with Microsoft, also. It's Microsoft - they understand there's infinite amounts of references online, they're not going to expect you to be a human computer, but they'd like to know that you can use one to find the answers you're looking for.
edit: The thing that can be stressful about MS interviews is that they're not scheduled. You go to one person, and talk for awhile, and then get a 10 minute break, during this break they discuss if they think you have any weaknesses, or whatever, if the next interviewer will try to find out if this is true or not. Your interview can end early if they don't think you're a fit, or it could go on for 4-5 different interviewers if you're doing well.