To improve the speller we worked with Silviu Cucerzan and Eric Brill from Microsoft Researchs Text Mining, Search and Navigation Group. Silviu and Eric have developed some novel techniques for using search query statistics and iterative transformation of query strings to improve spell correction. Their published paper on this topic Spelling correction as an iterative process that exploits the collective knowledge of web users goes into much more detail on some of the technical thinking that inspired the spelling correction system we built.
Btw, in September we posted about Eric Brill and the Text Mining, Search and Navigation Group's work in developing answer engine technology. You can also find a small collection of Microsoft publications about search here.
MSN's blog also explains more details on how its Inside Near Me Search feature works to try and deliver locally-targeted results.