Best you're going to get is an INDEX SCAN. So, even with an index, it still has to go through the entire index and look for existence. I suppose theoretically, a non-clustered index would speed things up for NOT EXISTS queries if the value searched is in the index, since SQL Server can load more actual records per extent than the clustered index (assuming a wide data page, of course).