Eu faço algumas coisas semelhantes (colocar atalhos no menu Iniciar para o rápido "Win + S..type nome (ou poucos caracteres) de atalho ..press digite" maneiras de carregar programas e scripts). Eu não notei nenhum problema com a nova atualização, mas aqui estão algumas coisas que eu tentaria no seu caso:
1) Faça um backup da pasta que contém seus atalhos. Exclua e reinicie o computador. Em seguida, copie-o de volta (e possivelmente renomeie-o). O pensamento aqui é que ele pode ajudar o índice de pesquisa a se reconstruir.
2) Adicione a pasta ao seu PATH. Aqui está um link sobre como fazer isso se você precisar saber como: Como defino as variáveis de ambiente do sistema no Windows 10?