I always say that Microsoft is a great place to have worked. It's great for learning how to ship real software (large and small) with all of the attendant processes and politics that go with it. You will learn what you think is important to take with you and what is important to leave behind. Both types of learning are important, because as you move to startups, you will have a hand in determining the equivalents in your new microcosm of that world.
One interesting quality I see from many people who have worked there is that there is a perception that life after (i.e., outside of) Microsoft is scary. That's partly because you can change jobs there endlessly and never actually leave. You can go from working on operating systems to large binary (client) applications to Internet apps to video games, etc. I've had to assure several of my friends that were contemplating leaving that the water outside is safe and warm. Every one of them has thanked me afterwards.
Another poster made a good point about some companies' HR departments not taking a second look at you. That's true. However, I generally wouldn't want to work at those companies anyway. I've never had a problem finding work at great places. In fact, I've never had to apply for a job since I left. If you're good, and your network is sound, people will reach out to you--degree or not. Microsoft is a great foundation on which to build your resume.