>If you add a NOFILTER to the query's you'll come to the conclusion that the query's with an index on DELETED() will be slightly SLOWER than the query's without an index.

I was scratching my head at why David's test was so different from mine, too. You have answered it, I think...I used NOFILTER in mine, which I almose always use in practice. As I noted, the results were extremely close (so close as to not matter, anyway) with & without deleted tag, SET DELE ON, no deleted records in my table of 500,000 recs, 20 MB.