Son dos cosas distintas, por un lado dices que a veces el procedimiento no funciona (a) y por otro lado cómo hacerlo más rápido (b).
a) En cuanto a que el procedimiento no funciona a veces, si revisas
la ayuda de la función DeleteFile, verás que habla de:
"...If the file cannot be deleted or does not exist..."
Por lo tanto puede ser que el fichero exista en disco, pero no se pueda borrar por otros temas (por ejemplo, porque esté bloqueado). En ese caso no podrás borrarlo y sería el caso que tú comentas.
b) Lo segundo sería cómo hacerlo más eficiente y rápido. El código no está mal conceptualmente (en cuando a funcionamiento), se hace un recorrido y se borrar los registros y ficheros. Lo que sí es verdad es que las operaciones de disco son "lentas" en comparación con el resto.
Si necesitaras más velocidad lo siguiente podría ser utilizar
Threads. En ese caso, podrías lanzar un thread para cada borrardo.
Se podría realizar el recorrido, borrar el registro y lanzar el thread para borrar los ficheros. En ese caso el programa no debería estar esperando a que acabara cada instrucción de borrado. Eso sí, tendrás que replantear la gestión de posibles errores.