I came in as a contractor. I tried to make it clear that they wanted me permanently, and they did.
I tried getting internships, applying through Monster, applying through the
www.microsoft.com/careers site, and never even got a single call back.
Be persistant, but not spammy. Continue learning technologies that Microsoft wants people to know, but don't over-focus on it. Having solid coding, debugging, and communication skills will qualify you for a lot of jobs at MS. I don't (and won't) have a deep
understanding of COM and I'm doing quite well as a dev. Having a deep understanding will help you get a specific job that requires it.
It helps to know someone at MS who can say positive things about your work.