This has happened to me with labels before, too. I'll do a search for all things that have a label and are in my inbox, and then archive them. I'll then go back to my inbox, and see that it missed something with that label. If I then repeat the search, I get zero results, even though it has the label, is in my inbox, and I can go back and find it. It's extremely frustrating.