Late last month, the Live Search Team blogged about their latest search experience enhancements:
part 1 and
part 2. As a user, the "results" speak for themselves. Since the beginning of MSN Search, the biggest complaint was in the relevancy of the search results which paled in comparison to Google's results. The evolution of its search engine is quite intriguing; unfortunately, the business has evolved to where it is an expectation as opposed to headline news. Also, the masses only seem to take notice when there is some new UI sexiness introduced or revamp.
While Search UI remains fairly unchanged and consistent throughout (although www.ask.com looks like they're trying to innovate on that front), it's the accuracy and the results that matter. Stemming is one area that can significantly boost search result accuracy. Entering into the wonderful world of text mining and analysis, a couple stemming algorithms used by open source frameworks are: KStem and Porter Stemming algorithm.
The subtle features such as stemming or synonyms analysis are what make the search experience so much better. So while these things fall far from the vision of NLP, it is a stab at "doing what users mean, not what they say!"