Presumably when you delete one of these files through explorer you don't get a prompt (other than the basic "are you sure").

A couple of things to try:
Take one of the files that is failing, open a command prompt and try to delete it using the full path, see if the delete works at the command line.

Try adding the "force" flags to the del command and see if it helps:
 Code:
Del $sPrefix+$sEntry+$sSuffix+$sFileToDelete /f /h


If that doesn't work then maybe follow the path of least resistance and get the users to delete their own files in their startup script.