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.