Search folders are convenient way to filter specific items in your Outlook. If you want to use them with multiple mailboxes however, especially shared ones, there are some catches.
First of all, Outlook will only allow you to create a new Search Folder for actual accounts, i.e. a mailbox that you have added as Additional Account and not as Additional Mailbox (via Automapping or Account Settings -> More settings -> Advanced). Unless you have added the mailbox as additional account, the “Search mail in” dropdown menu of the New Search Folder dialog will not list the mailbox in question.
Another important thing to note is that in order to actually access the Search folders of another mailbox, the mailbox needs to be accessed in Online mode. To make sure this is indeed the case, select any folder in that mailbox and take a look at the status bar – if it says anything different than “Online”, you will need to adjust the settings. Most likely, you will need to remove the “Download shared folders” checkbox under Account Settings -> More settings -> Advanced. (This only applies if you have added the mailbox as additional mailbox, if it is added as additional account there should be no issue with accessing the Search Folders.)
One last thing – having a shared mailbox added as additional account can impact the process of sending messages as or on behalf of that mailbox. What I see as the best option is to simply create a new Outlook profile and add the shared mailbox as primary account there, then configure any Search Folders you need. In your main Outlook profile add the shared mailbox as additional mailbox (or simply automap it) and make sure it’s accessed in Online mode. The Search Folders should then be available to you, and should you need to create new one or make changes to existing ones, you can simply switch to the other Outlook profile.