Hi David,
Our response times on an addressbook of 40.000+ users are usually well below 2 seconds, so your response time is definitely not normal. The lookup mechanism does a lookup in the ($Users) view, which means, for this application, your addressbook does not need to be full text indexed (not a bad idea to have it full text indexed in general though), but if your ($Users) view's index was discarded it would have to be rebuild before the search can return any results and that takes time. As that view is used by Domino itself continuously it's unlikely though that its index is ever discarded.
I think, like Steve said, check if your don't have a corrupt view index. If you have multiple Domino servers, check if lookups on other servers are faster. If so, rebuild the views on your addressbook on the slow server ("load updall -R names.nsf" when it's quiet). If not, check the index criteria on your ($Users) view. They should be on the default Refresh automatic and Discard if inactive for 45 days.
Good to know: Searches won't start until you have entered at least 3 characters. It waits a certain time before it will start the search to see if you will type any additional characters. This time is defined in the NP_Picker JavaScript library as NP_timeout. If you have more than 3 characters and haven't typed anything for 200 ms (the default in the demo app), it starts searching.
-- Martijn