What makes the "start menu" search find the app only on the second try?

When I search for an app in the Start menu, the first attempt often returns no result, but typing the exact same thing a second time finds it immediately. Why does the Start menu search only work on the second try, and what could be causing this inconsistent behavior?