Just stumbled across this one:
http://www.google.com/webhp?complete=1
It’s a Beta Service on Google.com and it’s using Ajax to „suggest“ as you type.
Nice.
Simply use the URL above and start typing something, make sure you are on Google.com and didn’t get switched to your Language, if you are in Europe.