Odd inconsistent behavior of SQL Server "IN" clause Query 1:

select count(UserID)
from users
where UserID IN (select UserID from otherTable)


Returns: 178

Query 2:: (simply changed IN to NOT IN)

select count(UserID)
from users
where UserID NOT IN (select UserID from otherTable)


Returns: 0

Query 3: (remove the IN-clause completely)

select count(UserID)
from users


Returns: 1047123 (over a million)

What? I can't... Even... 

The only explanation I have is my database in inconsistent/corrupted, I have to run DBCC CHECKDB or something.

PS. UserID is a primary key, so - no dupes.
NOT IN will not evaluate to true when one or more NULL values are returned by the subquery. 

Use NOT EXISTS to avoid this common gotcha. See this answer for more information and links to more detailed information.