Los accesos directos Window$ los trata como archivos de extensión.LNK, por lo cual pueden ser eliminados.
Lo que no te puedo comprobar es si esa función lo hace (Aunque debería sin problemas), porque aca no tengo Delphi como para hacerte una prueba
Puede haber, como bien comentaron, permisos de solo lectura en el archivo.
Siento no poder ayudarte más por el momento...
PD: Los comentarios de DarkByte no me parecieron del todo correctos, sin embargo, y dejando de lado mi interpretación sobre esos comentarios, debo decir que que existe una guía de estilo para una mejor convivencia en los foros que vale la pena leer. Eso sólo, chau...