Since you mentioned Windows, Microsoft made Ribbon which uses Vimperator-style navigation to make toolbars and buttons discoverable as long as you know one hotkey (Alt). It can also be hidden until triggered with a hotkey. This is miles ahead of most discoverability tricks in power user interfaces, including fuzzy command search which is not guaranteed to remain stable as new commands are added.

One downside to the ribbons that I see is that they somehow inverted the hierarchy between menus and toolbar buttons: Previously, menus were the slow but predictable way to find a command, and both toolbar buttons and keyboard shortcuts were just that - shortcuts. Menus were a sort of "ground truth" which commands existed. They also had a standard way to be navigable through the keyboard: You can press alt and then simply use the cursor keys.

With ribbons, the menus were gone and the toolbar buttons became the "ground truth", but in a much more haphazard way.

Fuzzy command search goes a bit back to menus, but as you say in a way that's much less guaranteed to be stable.