Eu encontrei uma solução básica. A mesma funcionalidade do ícone de pesquisa pode ser obtida fixando o ícone de pesquisa encontrado no menu Iniciar na barra de tarefas e movendo-o para a esquerda. Ele faz a mesma coisa e é independente das políticas, scripts ou configurações de registro aplicadas do grupo. Isso funciona com a atualização mais recente dos criadores de conteúdo.
O motivo para esse comportamento são scripts de logon de domínio, provavelmente definindo diretamente alguns valores do Registro.