MM-Suggest provides AJax autocomplete with fuzzy matching that’s tolerant of misspellings and word reorderings and that can scale to millions of records.   A German shopping site that uses their technology is Billiger.  A nice improvement over the typical online search experience.