Como sugerido por @doug nos comentários, eu precisava sair e entrar para que a alteração fosse aplicada.
Remover o ícone "Show Desktop" funcionou imediatamente, e é por isso que eu esperava que o atalho também fosse removido imediatamente. Não foi.
Ainda é muito estranho que o atalho estivesse ativo, mas não visível em nenhuma das ferramentas de configuração que mencionei na pergunta. Parece que o atalho foi codificado juntamente com o ícone ativar / desativar. Por que o ícone apareceu na minha última atualização do sistema também é um mistério.