Oddly enough
I wrote something similar to this for a CMS module. If you were adding a book to your store you could start typing the "contributor" name (might be the author or illustrator for instance) and it would pull up an auto-complete type suggestion box to the right of the text input box. So you type "Jon" and it pulls up all the "Jones" and "Jonathon" records and so on. Obviously this is of a much more limited scope with a much smaller data-set and even then I ran into some browser quirks and performance issues along the way (it works very well now thanks).
I'm sure Google's huge team of codemonkeys will be able to sort it - what I'm not convinced about is the NEED for it. I only really type searches into the Google page itself when I'm refining a search I've already instigated through the browser's in-built search bar - and if I'm refining a search its because I didn't narrowly enough define the parameters in the first place. That being the case, why would I want Google to expand the parameters of my search with irrelevancies whilst I'm attempting to refine the search?
I suppose, in a way though, if Google are storing everyone's search results this will add a lot of white noise to their lists... imagine searching on oooh, "Goldfinch" for instance.
...
Gold => all results relating to gold and "gold-diggers", gold teeth, golden showers(!) and so on.
...
Goldfi => Goldfinger, Goldfish, Goldfinch, plus "Goldfi" as company/personal names and web handles.
...
Goldfin => Goldfinger, Goldfinch and all the company/names and handles.
...
Goldfinch
So, on a search for an innocuous common garden bird, I'm apparently a golden toothed, money-grabbing perv who likes being pissed on by James Bond bad-guys? Actually ... ;)