According to MSFT's book on database development Exam 70-433: Microsoft SQL Server 2008 Database Development:
Neither leading wildcard characters not NOT logic allow the query optimizer to use indexes to optimize the search. For optimal performance, you should avoid using the NOT keyword and leading wildcard symbols.
So I took that to be
NOT EXISTS etc
Now with regards to this SO question, I thought that the chosen solution by @GBN would violate the statement given above.
Apparently, it does not.
So my question is Why?
Save me from confusion :)