Search for a contact

I am currently using an SBS2000 Server and my notebook is
running Office 2003 with XP Pro
I am using Outlook and Exchange on on server.

I have about 11,850 contacts in a public folder contact
folder all contacts are sorted with categories.
When we have a customer call in and we have to search for
his cont file it takes ages to search.
IS there a way we can reduce the search time? or is there
a way we can create a form that will search on the field
we are looking for i.e: First name or email address or
telephone number etc...

Appreciate your help in this matter.
Regards,
Kunal