This may be difficult to understand at first, so I will do the best I
can explaining.

We provide hosted email box's as a partner with WWW.123together.com.
Since its release, we set up our clients with outlook 2003. We have
one customer that uses outlook in more ways than I imagined possible.
That's beside the point. His current issue is:

While adding an appointment to his personal folder (or mailbox if you
prefer), he utilizes the Contacts and Categories section at the bottom
of the appointment window. Although he is aware of alternative
methods, he prefers to type in a contacts name and press CTRL-K. This
results in a slow search which eventually provides a small dialog with
matches from his personal contacts and a "master contact list" located
in public folders. The problem is, it takes way too long. He is very
disgruntled since she has two companies to one and does not find this
extra time waiting for the computer appealing.

To answer your presumed question: your office is setup with a full
T1. yes, outlook is configured for cache mode. And yes, public
folders are setup for cache mode. There are roughly 2000 contacts in
the shared public folder. The public folders are shared with six
other employees inside the same local network. This office is located
in Florida while the hosted exchange server is located in
Massachusetts.

My first thought was that the distance between clients and server, the
number of clients, and the number of contacts in public folders is
simply a bottleneck. However, after seeing it for myself, it did take
an extremely long time (60 seconds) to return results.

Can anyone suggest settings I need to check/adjust to improve its
performance?

Any help would be appreciated.