Outlook cache exchange mode must be disabled to be able to search in all subfolders.
Open menu “File”, select “Info”, “Account Settings” and once again “Account settings”. Then select your mail box and click “change”
Deactivate Option “Use Cached Exchange Mode” (if possible):