Simon,

An index on deleted is not universally beneficial. When a commnad, like locate or SELECT, is used to process a medium sized (1,000,000 records or so) an index on deleted() can improve prefomance when set deleted is ON.

SET DELETED ON is equivalent to SET FILTER TO NOT DELETED() and Rushmore can improve performance for filters.

That said, with very large tables there are situations where Rushmore actually decreases perfomance. If the condition being optimized is one where the distribution of values is extremely uneven (like a table of 10,000,000 record where only 3 are deleted) then rushmore's need to cache the entire index can hurt performance.

The only way to tell if an index on deleted is going to be beneficial is to test your code with samle data that has approximately the actual numbers of record with a distribution of values that matches what the actual table will probably have.