This feature was introduced on November 12, 2001. It was part of a whole set of new features, the dynamic clustering and the Fast topics navigation features. Additionally they released the first permanently refreshed News search on the web. It was groundbreaking and made the competition quite nervous.
The query rewrite is based on lingusitic analysis. It's an attempt at better understanding and answering of user queries. It's a step into what several engines have been dabbling with: handling natural language.
We have added linguistic analysis of queries that detects common phrases and automatically quotes those. Our phrase dictionary includes the names of people, places, and things. Also, we have added anti-phrase detection to remove non-interesting parts of your query. ... We're no longer just matching search terms - we're interpreting the user's intention and displaying results accordingly.
>a lot of fancy features for something that is said to be a testbed
Actually many people feel a search engine for the masses shouldn't have too much features, at least not visible features. Most users never change anything on a search engines options panel, most don't know even basics like adding quotes. One reason to make those features very visible at ATW was for customers, portals from all the world, to see the tech in action.
The fact that ATW has become a favourite of information pros was a mere side effect.
But then - I don't think the ATW team would object to a little word of mouth effect :)