Parece que entendeu o padrão Strategy, a motivação, etc. Não sei se acha que deve usar em todo lugar. Tem caso que pode ser melhor centralizar as estratégias sem deixar ninguém inventar moda naquilo. Se achava, saiba que tudo depende do requisito real.
Mesmo que pareça um boa ideia, em alguns casos, é aquela coisa, você cria a infra porque vai que um dia precisa, mas nunca precisa, ou até você usa, mas se fizesse de um jeito simples dava na mesma. Muitas dessas práticas que falam por aí é pra projetos muito grandes com tempo de vida muito longo e que realmente muda muito. Muitas dessas recomendações é para compensar deficiências da orientação a objeto, o que talvez indique que o erro de projeto seja mais embaixo. Lembrando que estou apenas dizendo para considerar isso, não que deva abandonar a ideia do Strategy, ele é bem útil em vários casos.
Você coloca um caso muito comum de uma alteração (adição) de uma estratégia em um objeto e isso refletir em outro objeto. Por exemplo ocorre em MVC (mudou algo modelo é quase certo que terá que mudar algo na visão e talvez no controlador). E é isso mesmo, você tem que ter uma forma da UI também permitir a adição de uma estratégia nova, talvez usando algum padrão em conjunto como o Command.
Mesmo que faça algo que pareça simples e não precise mexer no código para colocar na UI a opção nova, de uma forma ou de outra terá que inspecionar o código ou registrar que tem uma estratégia nova a usar. E nesse caso pode ser que a UI precisará de algum texto ou outra informação que só faz sentido pra ela, e isso deverá estar disponível na própria estratégia que você criou, e aí talvez viole o S so SOLID :) Pode ser que não, mas não é certo para todos os casos, e depende da tecnologia usada.
Alternativas
Já vi implementações que montam um conjunto dessas situações todas, mas não sei se é algo bom, eu precisaria testar pra ver se funciona bem, nunca o fiz pra poder falar.
Um objeto pode ter tudo o que pode estar relacionado à essa estratégia. De certa forma é uma ampliação do padrão Strategy. É esse padrão, mas ele cuida de mais coisas além da estratégia básica, ele cuida de estratégias relacionadas, e esta é uma forma de ter todas em um lugar só, assim você não esquece de implementar uma delas.
Você teria uma classe abstrata ou interface que diz tudo o que precisa e cada estratégia implementa tudo. É exatamente o padrão mas combinado. Isso ajuda no O do SOLID, mas viola o I e S do mesmo.
Talvez dê pra fazer várias interfaces e só na concreta dizer que vai implementar todas, o que não viola mais o I, mas se você esquecer de colocar uma das interfaces como obrigatória dará problema.
Talvez você possa ter o meio termo, ter várias interfaces e uma que herda de todas e assim obriga todas elas (na prática não a usará em lugar algum a não ser na implementação da sua classe pra obrigar todas estratégias sejam implementadas sem esquecer de nenhuma, mas pro consumo usará as interfaces individuais e segregadas.
Talvez crie uma ferramenta de análise estática para garantir que está tudo ok antes de compilar, assim pode manter tudo separado e ter alguma segurança.
Quem sabe precise de um teste de unidade para garantir que todas estratégias relacionadas forma implementadas mesmo em estratégias que você nem conhece ainda. Não sei se esses frameworks de testes possuem facilidades para isso ou tem que fazer na mão, o que não é tão simples, nunca fiz algo assim.
Uma estratégia que eu já usei em caso parecido foi geração de código, mas só funciona se é tudo muito padronizado. Reflexão também funcionaria mas tem um custo de runtime que eu não gosto, não só pela performance, mas deixa o sistema menos robusto e propenso a quebras no momento do uso, embora testes ou analisadores estáticos podem minimizar isso, mas sempre vai complicando, e aí o gerador pode ser melhor opção mesmo.
Ou pode fazer só a convenção mostrada na outra resposta, e torcer para o programador que criou a nova estratégia fazer tudo certo e não esquecer de nada. Parece ruim, mas há casos que é melhor assim, que começar querer fazer o contrato ser muito certinho pode complicar demais. A estratégia do parágrafo anterior pode funcionar em um caso e não funcionar em outro, ou pode adicionar complexidade sem ganho real.
Conclusão
Parece complicado e você fica em um sinuca de bico e não sabe o que é melhor? Bem vindo ao mundo real do desenvolvimento de software onde não existem soluções completamente corretas em todos casos, você escolhe o mal menor.