The following batch executed on different instances of SQL Server 2000 illustrates the problem.

  select @@version 

  create table a
  (a int)
  create table b 
  (b int)

  insert into a(a) values (1)
  insert into a(a) values (2)
  insert into a(a) values (3)
  insert into b(b) values (1)
  insert into b(b) values (2)

  select * from a
  left outer join (select 1 as test, b from b) as j on j.b = a.a
  where j.test IS NULL

  drop table a
  drop table b


Output 1: 
Microsoft SQL Server  2000 - 8.00.194 (Intel X86) 
       Aug  6 2000 00:57:48 
       Copyright (c) 1988-2000 Microsoft Corporation
       Developer Edition on Windows NT 6.1 (Build 7600: )


(1 row(s) affected)

(1 row(s) affected)

(1 row(s) affected)

(1 row(s) affected)


(1 row(s) affected)

(1 row(s) affected)
a           test        b
----------- ----------- -----------

(0 row(s) affected)



Output 2: 

Microsoft SQL Server  2000 - 8.00.2039 (Intel X86) 
       May  3 2005 23:18:38 
       Copyright (c) 1988-2003 Microsoft Corporation
       Developer Edition on Windows NT 5.2 (Build 3790: Service Pack 2)


(1 row(s) affected)

(1 row(s) affected)

(1 row(s) affected)

(1 row(s) affected)


(1 row(s) affected)

(1 row(s) affected)
a           test        b
----------- ----------- -----------
3           NULL        NULL

(1 row(s) affected)

If someone encounters the same problem - make sure you have the SP installed!