David,

Though i know that an index on deleted will help you to get full optimization, it gives no garantee that the general performance will increase. I've the impression that the pressure to use an index on deleted() is not based facts, but on the goal to have full optimization, by which (in my opinion) users are mislead.

If you've an index on deleted VFP has to maintain an extra index which leads to decreasing performance when you insert or update records in a batch.

Second, If the table you're searching in does not have many deleted records, the gain of performance would be very small. In my apps i never have many deleted indexes in large table for two reasons.
1 - it takes valuable disk space (2 GB limit)
2 - it decreases performance, even if you have an index on deleted() because of the larger table.

Now i can hear you say, but i can't schedule a pack procedure because the system runs 7 days a week. But even then you could recycle deleted records.