It's definitely a bug nothing to do with settings, so don't bother changing settings.
I had the same issue for over a week and was going crazy. Reinstalling as other people say might work but I'll tell you what worked for me and would be happy to know it worked for you too.
I was in my outbox folder waiting for an email to be sent and I noticed there was a search box on the right. So I decided to make a search but no in the outbox folder (as it was empty) but I changed the folder I wanted to search from "current Folder" to
"all outlook items" (not sure whether that made any difference but I'm telling you exactly how it worked for me). After the search all the relevant results came up as they should and then I noticed that the instant search box was back where it used to be,
in the main inbox folder.
Please let me know if it did work for you as I can feel your frustration..
