In DM-29849 we have made dataset deletion during collection pruning significantly more efficient. As implemented it should be faster than what you previously have experienced (with fewer confusing messages about missing files or inability to remove them).
If you have your own gen3 registry (ie not one of the main NCSA or IDF registries) you can make deletion even faster by running this command:
CREATE INDEX file_datastore_records_idx_path ON file_datastore_records (path);