Danny Sullivan's detailed look at how Google's auto-complete and instant search, which seems to be populated by a combination of many recent searches and long-term frequent searches. They have an inconsistent policy on removing negative terms from the suggested list. He thinks they should just remove them without fuss.
These examples emphasize how enterprises and web sites should keep very strict control over their autocomplete (and spelling) suggestions, rather than rely on technology.
In e-commerce, it's much better to find something than nothing. Spellchecking and other tools for inexact matching can improve results for the long tail of unique and near-unique queries. Exorbyte reports increases of conversion from 5% to 20% - at least somewhat related to their error tolerance.