I was able to get the search feature to work by taking these steps:
"Enable Cached Exchange Mode . Even with that enabled, by default it doesn't include Public Folders. To get the search to work on Public Folders, you need to add the specific public folder to your favorites and then in the advanced account settings tab, select "Download Public Folder Favorites" Once the folders have been downloaded, they will be indexed and should return answers in your search."
However when I click new message and click on the "to" field and search for a public contact that way it will not work. I also selected public folders and it still will not pull up the list.