>An index with the expression not deleted() can make all sorts of queries very slow.
>
>An index with any other expression, but filtered on not deleted(), will simply not be used for Rushmore Optimization. You may sometimes need this index, for example, for a client code, if you want to declare it as candidate (or primary, depending on your design), and the user supplies the code. In this case, it may be necessary (in some cases) to have a second index, not filtered and not candidate, on the same expression, for use in Rushmore Optimization.

It's changed in VFP9:

"INDEX ON NOT(DELETED()) optimizes NOT(DELETED()) and DELETED() query conditions. In versions prior to Visual FoxPro 9.0, only DELETED() was optimized".

"INDEX ON ... FOR DELETED( ) or INDEX ON ... FOR NOT(DELETED()) optimizes DELETED() or NOT(DELETED()) query conditions respectively when INDEX ON DELETED() or INDEX ON NOT(DELETED()) is not present".