Finally we seem to have some solid information on why some indexes (particularly deleted) should not always be used. The slowdowns in SQL can be quite large over a network. Check out page 34 in the May FP Advisor, there's what I think one could call a "significant" article on Rushmore and how indexes are used.

The conclusion is that for SQL, the deleted index, and any other indexes (such as logical) that are not "widely dispersed" amongst the data, can cause major slowdowns over a network. My testing was done locally, so please discount my findings that deleted index did not slow down (nor speed up) the queries. Testing must be done over the network, as this article has done, to truly show the delays caused by "over-indexing."

Anyway, a definite must read...