Well, better late than never. Google maps API v3 now provides address autocompletion.
API docs are here: http://code.google.com/apis/maps/documentation/javascript/reference.html#Autocomplete
A good example is here:
http://code.google.com/apis/maps/documentation/javascript/examples/places-autocomplete.html