As @bpasero suggested, I'm opening an issue to suggest adding fuzzy search in the palette for commands as well.

He had an issue with this though, so it could be enabled with a user setting. But I am unsure about his concern.

The issue with fuzzy matching is that you also need to do fuzzy sorting: more relevant results to the top. However for the command palette we chose to sort entries by name to keep the result list stable and memorable. Enabling fuzzy for commands would change the sort order for each search you do making it harder to learn the list of available commands.

I don't understand how the sort order is relevant when you are looking for a specific command or set of commands. Let's say I would like to look for all Markdown related commands (which start with Markdown:): in Sublime, I would only type md:, removing practically all unrelevant commands from the results list. The results however would still be sorted by names. Am I misunderstanding his issue?

Once you're used to search in a fuzzy pattern (often with shortened words like msg for message), it is very awkward to go back to typing complete words.