>I have a table that has around 66% deleted records, and is accessed with SET DELETED ON.
>
>Users complain it is slow when accessing it.
>
>Would it be wise to add DELETED() Tag?
>
>Thanks
>Kev

Yes, I'd recommend indexing on DELETED().
There has been a lot of research in the last few years into the benefits of the DELETED() tag. In large tables with a small percentage of deleted records loading the DELETED() index takes longer than weeding out the deleted records. But in this case, I think it will help. And if it doesn't, just remove the tag.