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.