Amanda,
I believe I have found the reason for the search failure and will be trying a different approach. After quite a bit of research, what I found was that in order to get Outlook to search everything including Shared Mailboxes, you need to do this.
You have to use the Outlook "Add Account" button, enter the shared mailbox address and no password. Then, when prompted, use the UPN/password for the person with Full Access permissions to the shared MB. This will then add the shared MB as an additional Outlook account and once done, allows you to use all search options on all mailboxes.
I have requested credentials for our shared MBs so I can try this. If this works, it hopefully solves the problem. I will post a reply as soon as I know results, but from what I've read, this should work.
--Cliff