Este é um tópico antigo, mas talvez alguém possa se beneficiar do meu comentário.
Existe um serviço chamado Distributed Link Tracking Client que localiza um arquivo que foi movido ou renomeado em um compartilhamento de rede NTFS ( KB312403 . Isso funciona também para atalhos de shell e links OLE.
Tivemos um problema semelhante quando movemos pastas em nosso compartilhamento DFS. A experiência foi que, depois que as pastas foram movidas, os atalhos nas áreas de trabalho dos usuários foram alterados de \ dfsvirtualname \ sharename para \ realservername \ sharename. Sim, os arquivos foram encontrados apenas uma vez. Na próxima vez que a pasta foi movida (como arquivada para uma pasta chamada 2014, etc), os atalhos quebraram.
O problema que você tem com alguns arquivos pode ser que esses arquivos já foram movidos no passado e o Cliente de rastreamento de link distribuído os encontrou, alterando o link para uma referência completa \ realservername \ sharename e agora não é possível encontrar o arquivo movido.