I think (and again this is only theory) the optimizer will use the DELETED tag when whenever SET DELETED = ON. To check for any gains of speed use we can use the example of David and delete (randomly) about 50% of the records and run the tests again.
>
>I'll predict that the the time to complete this test with a tag on DELETED() would be between 60 - 70% of the time to run it without a tag on deleted.

You are more right than even you thought, Walter. I just tested my 500,000 rec table with this, all NOFILTER, SET DELE ON:

1) deleted 1/3 of recs with MOD function.
2) result query with Deleted tag ran guess what? Exactly 33% faster.

Here is something else: With SET DELE OFF, there is no advantage with the deleted index unless DELETED() is part of Where. Then you get the same performance increase as above.

I'm pleased to get to the bottom of this, now we can really index on deleted in the appropriate tables. This means none of my large ones, which are all readonly, but some of my medium ones which may contain many deleted records.