During cleanup I ran

del /q "%UserProfile%\Mine dokumenter\Mine bilder\Eksempelbilder.lnk"
del /q "%UserProfile%\Mine dokumenter\Mine musikk\Eksempelmusikk.lnk"

Paths are correct -Norwegian Windows XP. The shortcuts was still there after computers last reboot.

I tried to manually run the two lines from cmd and the shortcuts were removed... Any idea?

Perhaps the cmd exit beforce these two line, for example because another cause an error and exit without running these lines, try to insert a "pause" and echo on to look all the command and the result.

That's not it

When you run your cmd ? This must run in a session .. not at cmdlines.txt for example ...

Try removing the folders from the %AllUsersProfile% first and then delete the link. In my cleanup command I use the following

RD /S /Q "%AllUsersProfile%\Documents\My Music"
RD /S /Q "%AllUsersProfile%\Documents\My Pictures"
RD /S /Q "%AllUsersProfile%\Documents\My Videos"
DEL /F "%UserProfile%\My Documents\My Music\Sample Music.lnk"
DEL /F "%UserProfile%\My Documents\My Pictures\Sample Pictures.lnk"
DEL /F "%UserProfile%\My Documents\My Videos\Sample Videos.lnk"

Try this vbs script I have used the directory you have provided, I do not

have a way to test this.

Save As Remove_MusicLinks.VBS

On Error Resume Next

Dim Act, Fso, UP

Set Act = CreateObject("WScript.Shell")

Set Fso = CreateObject("Scripting.FileSystemObject")

UP = Act.ExpandEnvironmentStrings("%UserProfile%")

Fso.DeleteFile(UP & "Mine dokumenter\Mine bilder\Eksempelbilder.lnk")

Fso.DeleteFile(UP & "Mine dokumenter\Mine bilder\Eksempelmusikk.lnk")