As someone who has had no trouble getting interviews in the past (outside of the year or so post-dotcom bust), and more recently as a hiring manager who has just as much trouble finding candidates *worth* interviewing as you seem to be getting those interviews, here's the best advice I can give out:
1. Be honest about your address and intentions. If someone applies to my "local applicants only" job with an address in CA I don't even bother to read the resume. However, if you mention in your introduction email (cover letter?) that you want to move to the area and plan to be making a trip up in the next couple of weeks ("to visit some friends", "for a couple of interviews", whatever), I'll give your resume the same consideration as I would to a local candidate. I might even fast-track a phone screen if you look good, so I can schedule an interview to take advantage of that time you'd be here. Do your best to make your trip description emphasize how serious you are about looking for a job in the area -- it will bypass the concern a lot of small companies have paying to fly you into town for an interview (not worth it with so many great local candidates), and should hopefully prevent you from sounding presumptuous about expecting an interview.
2. Find some good recruiters. I don't know a single tech worker who enjoys dealing with recruiters (most put off the same vibe as the stereotypical used car salesman) but there are a lot of VC-funded startups that hire exclusively through recruiting firms. Reach out to big guys like greythorn and volt, and do some searching on linkedin and other sites for smaller firms (which often have much more interesting work). Reaching out directly to them will help you get the message across that you want to move, and in turn they will help convince the hiring manager that you're worth talking to despite currently being out of state.
3. You mentioned Seattle and MS in the same description. Be aware that there is a giant invisible line down the middle of Lake Washington. Though there is some MS stuff (at least on the web side of things, which is what I know best) in Seattle, there is a lot more of it on the East Side (Bellevue, Redmond) closer to Microsoft itself.
4. It may help to get a local phone number, but honestly if you mark your non-206 number as "cell" and direct eyes toward your email address, I can't think how it would hurt your chances. FWIW, unless asked on a job application form at a big company, I'm not sure I've ever given my phone number out to a prospective employer until asked for it in order to schedule a phone screen.
5. Yes, there really are that many good candidates in the area. You're competing with locals who are more readily available for interviews or followup interviews, so you need to stand out more than they do. And it's not just about weighing the costs of bringing a non-local candidate in for an interview -- I personally hate giving video interviews and will do everything I can to avoid them (I get so much more out of the interview if I can actually interact with a candidate; after all, personality-fit is as important as technical competence).
6. On the other hand, there really are a lot of good jobs here, too (Amazon's hiring spree high pay has made it a pretty competitive market, too). Consider broadening your skill set. I know there is often a wide cultural gap between the kinds of devs who focus on MS vs Linux, but if I'm just looking for a good developer/engineer rather than a language expert, I'll be much more interested in you if your resume has more than just the one stack (Ruby+dotNet, dotNet+Java, etc). You could also take this as a "don't complain about picky companies if you're limiting yourself to a single technology subset".
7. Be willing to work contracts. Microsoft itself is well-known for preferring to hire people through staffing agencies (corp-to-corp contract) rather than through direct hiring, and they're not alone among the larger companies. The staffing company becomes your employer while you work the contract (avoid 1099 contracts unless you fully understand the tax implications), and you don't have to feel too bad if you leave for a better gig a few months into the contract.
Anyway, I hope this helps someone.