Eu suspeito que o problema é que seus usuários não administrativos estão tentando excluir atalhos que existem na área de trabalho comum (C: \ Users \ Public \ Desktop). Somente administradores podem fazer isso.
Geralmente, a versão do seu DC tem muito pouco a ver com quais permissões e direitos existem em suas estações de trabalho. Claro, você pode ter todos os tipos de configurações de diretiva de grupo e modelos de segurança que alteram as configurações de segurança da estação de trabalho, permissões de arquivo, etc. Estou assumindo que seu ambiente não é tão altamente personalizado.