Hello Andrus,
If you have a large table and you SET DELETED ON, then you need the index on DELETED() regardless of how many records are deleted. If you do not have an index on DELETED(), VFP has to inspect each record to determine whether or not to present it. Thus, you lose all Rushmore optimization.
Regards, Chaim