Walter,
When SET DELETED is ON EVERY record must be checked for delte status regardless as to whether it is deleted or not. The number of deleted records is not important, it is only the set deleted that is important. Set deleted on with no deleted records still requires that VFP check every record for deletion only to find out that they aren't deleted.
In my testing with a table of 20,000 records and 2 deleted records I get a 10% improvement with a tag on deleted() the same is true if there are no deleted records.
The performance change was similar with 10,000 and 100,000 records although the more there are the bigger the difference until one reaches the limit of memory for holiding the index.