I doubt auto-complete should be your #1 focus...

There is a huge opportunity now more than ever to take over search.

The real goal of a search engine is to provide relevant results. Google has 100% lost site of this and this is where you and the rest of the players have an opportunity.

Make your results 100% unbiased. Google's results are littered with their own biased content coming from Places, Youtube, Google Books, etc.

No one wants to see that. Google has lost site of the user experience as they need to grow revenues. It will ultimately come as a cost to them.