In my case (using Outlook 2010 with Office365 server) I had a shared folder on Office365 that was included in my folders list because it has the Auto-Mapping attribute set for me.
The primary mailbox whose coattails this appeared on was set to cached exchange mode, and I was unable to search all subfolders, and no Search Folders appeared under the shared mailbox.
After going to the "Advanced" tab of "More Settings..." in "Change Account" in the "Cached Exchange Mode Settings" group I unchecked "Download shared folders", saved the changes and had to restart Outlook.
After that, the "Search Folders" appeared under the shared mailbox, but I was still unable to select the shared mailbox or any of its folders for "Search mail in:" of the "New Search Folder" form.
However, by clicking in the search box, the Search Tools ribbon would appear and I could choose 'All Subfolders" there. Doing this at the shared mailbox root disabled the "Unread" choice from the ribbon, but I could type read:no in the search box and have it work. Unfortunately there does not seem to be any way to save this type of search.