We have been working on a replacement autocompletion API that is more forgiving than a strict prefix search. The scoring algorithm's have a long way to go but we have the first run through of building the completion index for enwiki so i thought i would share:
Here are a couple examples, feel free to change the text= around to other things.
Don't stress out too much over the scoring yet, we know it needs some work and have plans to integrate page view information in here to help more popular articles rise the the top.
Erik B