I have made some quick bench test for table with 160K records. There is really huge effect by SET DELETED setting: some simplect queries run for 20sec if ON against nothing if OFF. But I didn't see any particular difference in regard to overall performance like SKIP,GO,SEEK etc.
So, probably it's not a bad idea still have SET DELETED ON and just reset it temporarily before running SELECT statement which will use DELETED tag:
SET DELETED OFF
SELECT ... Where ... NOT IN (SELECT ... Where Deleted())
SET DELETED ON