Мне сложно сказать замедляет ли 'not in' выполнение работы, я просто поделюсь тем, что я заню, надеюсь это поможет найти ответ.
Если смотреть по плану выполнения, то увидим, что 'a in (b1,b2,...bn)' заменяются на выражение: (a = b1)or(a=b2)or...(a=bn). 'not in' - аналогично. Самое интересное получается, когда множетсво в правой части становится большим(я провнрял на SQL2K). Итак, если в множестве более 30 элементов, то оператор in заменяется не на ()or()... а на соединение с временной таблицей, составленной из множества. А 'not in' сервер продалжает трактовать как ()or(). Поэтому я предполагаю, что на небольших множествах все работает быстро. Если же множество велико, то все зависит от скорости вычисления условий ()or(). Я, честно скажу, не знаю насколько эти условия трудны для сервера.