Autocomplete isn't a big difficulty. We have auto complete enabled on some of the areas of the site here, especially tagging but that's only visible to the authors of articles.
Doing autocomplete on the search engine isn't going to get a high priority from me right now until a lot of the more urgent things get done.
