Outlook 2002 and Exchange 5.5

I need to be able to have users, while using Outlook 2002 on an Exchange 5.5 (SP4) server, have the ability to search through everyone’s mailboxes for messages, replies and the like using the advanced find feature of Outlook. Each user has access to the same public folder in addition to their own mailbox. I suspect it is a permissions issue somewhere either in Outlook, or in Exchange, but am unable to find a solution quickly. Thanks in advance.