Doing an autocomplete for that is no problem. Just use YUI autocomplete and set up a remote JSON data source.

That's what we do, and we have millions of names to complete: http://www.trailbehind.com

Here's the YUI library: http://developer.yahoo.com/yui/autocomplete/

I can send you the code for my autocomplete widget if you want. Email me at andrewljonson [at] trailbehind [dot] com