Proper Index for WHERE X  1 AND Y  1 ORDER BY Z
In general it is not possible to use an index seek on a condition x &lt;&gt; 1 and y &lt;&gt; 1. 

With an index on x,y the best you can do is convert it into two range seeks (x &lt; 1 and  x &gt; 1) with a residual predicate on y &lt;&gt; 1 (and this wouldn't be able to use additional index key columns to avoid a sort)

For a bit column as it can only have three values. 0, 1, NULL logically WHERE bit_column &lt;&gt; 1 is equivalent to  WHERE bit_column = 0 but seems SQL Server doesn't take advantage of that here and convert the &lt;&gt; to = conditions for you.

Adding a couple of check constraints does the job though even though these are apparently redundant in that they don't actually restrict the allowable values for the datatype in any way (for NULL if a check constraint evaluates to UNKNOWN it counts as passing)

CREATE TABLE MyTable
  (
     Foo     INT,
     IsFlag1 BIT NULL CHECK (IsFlag1 IN (0, 1)),
     IsFlag2 BIT NULL CHECK (IsFlag2 IN (0, 1)),
     SomeId  INT
  );

CREATE NONCLUSTERED INDEX ix
  ON MyTable(IsFlag1, IsFlag2, SomeId)
  INCLUDE (Foo); 


The plan now does show a seek on IsFlag1 = 0 AND IsFlag2 = 0



Or alternatively this filtered index also avoids the need for a SORT

CREATE NONCLUSTERED INDEX ix 
           ON MyTable(SomeId) 
           INCLUDE (Foo,IsFlag1, IsFlag2) 
           WHERE IsFlag1 != 1 and IsFlag2 != 1


It does a scan of the filtered index (the qualifying rows ordered by SomeId) with a TOP to stop scanning after the 1,000 rows are retrieved. IsFlag1, IsFlag2 are INCLUDE-d in the index to avoid an unnecessary look up that occurs without this.