Estou inclinado a pensar que "Esses itens não são encontrados na pasta para a qual o menu Iniciar é redirecionado" é o problema e que, na verdade, está sendo redirecionado para outro lugar.
As suas contas de usuário estão tão bloqueadas que você não pode clicar com o botão direito do mouse nos itens do menu Iniciar e depois verificar as propriedades para ver onde elas estão localizadas? Você pode desativar essa configuração para um teste?
Quantas políticas existem e quanto escopo você tem para testar? Você pode desativá-los um por um para descobrir qual deles está causando esse efeito? Você procurou por entradas de preferência de GPO que só se aplicam a condições?
Caso contrário, eu estaria analisando o Monitor de processo da SysInternals Se você puder fazer login no computador, execute o ProcMon como administrador, clique em um desses itens do menu iniciar e pare a captura. Em seguida, pesquise os resultados para .lnk e procure por explorer.exe acessando-o. Isso pode te mostrar.
Se os computadores estiverem muito bloqueados e você não puder executá-los como administrador, poderá executá-los remotamente com alguns ajustes, por exemplo, link e, em seguida, você pode configurá-lo em execução antes do login, registrar o que o Explorer acessa e depois vasculhe os resultados.