The use of NOT logic in relation to indexes
NOT IN (SELECT ...) and NOT EXISTS (SELECT .. WHERE correlation..) are "Anti Semi Joins". That is, recognised set based operations
WHERE NOT (MyColumn = 1) is a filter that requires all rows to be looked at


For more info, see:


Craig Freedman's "Introduction to Joins" 
Wikipedia "Relational algebra, Antijoins"


Edit: for completeness

LEFT JOINs often perform worse. See http://explainextended.com/2009/09/15/not-in-vs-not-exists-vs-left-join-is-null-sql-server

This same site notes that in MySQL, NOT EXISTS isn't optimised like other RDBMS and LEFT JOIN is better

In SQL Server, I know from experience that LEFT JOIN doesn't run as well as NOT EXISTS. You also often need DISTINCT to get the same results which another processing step.