you doing it wrong,
after you press "WinKey" you can immediately press keyboard's keys for search, as added bonus: you can still view your other works as it wont be obscured by screen full of tiles.
I said I hated the Start menu (ala 7 and earlier) - I have zero issues with the StartScreen. The searchability of said screen is something I pointed out way back in the Windows 8 Developer Preview.
The reason I despise the return of the Start MENU is at this point all it does is screw over third-party developers (not alone Stardock) - whether it is any more usable than said third-party utilities I could care less about, for reasons i explained.