Walter,
If you don't have SET DELETED ON, the index is not so important. But if you do have SET DELETED ON, then the index is important and it does not matter what percent of the records are deleted. The only case where the index on DELETED() is not important is if you very few recrods or if SET DELETED is OFF.
Regards, Chaim