Sql 2005 Weird Behavior

We have an interesting problem. We are attempting to migrate from sql 2000 to sql 2005. the schema we have is exactly the same. the new 2005 box is more powerful than our 2000 box.

here is our schema:

tbl_Items
ItemID int pk
ReferenceID int
sessionid varchar(255)
StatusID int

tbl_ItemsStatus
statusid int pk
isinternalstatus bit

there is an index on (ReferenceID, SessionID, StatusID) and (SessionID, StatusID)

this is the query:

DECLARE @referenceid INTEGER
SET @referenceid = 1019

SELECT MAX(i2.itemid)
FROM tbl_Items i2 (NOLOCK)
JOIN tbl_ItemsStatus s (NOLOCK)
ON i2.StatusID = s.StatusID
WHERE
s.IsInternalStatus = 0
AND i2.referenceid = @referenceid
AND i2.sessionid IN (
SELECT i3.sessionid
FROM tbl_Items i3 (NOLOCK)
WHERE
i3.referenceid = @referenceid
AND i3.status <> 7
AND i3.status <> 8
AND i3.status <> 10
AND i3.itemid IN (
SELECT max(i4.itemid)
FROM tbl_Items i4 (NOLOCK)
WHERE i4.referenceid = @referenceid
GROUP BY i4.sessionid
)
AND i3.itemid NOT IN (
SELECT MAX(i7.itemid )
FROM tbl_Items i7 (NOLOCK)
WHERE
i7.referenceid = @referenceid
AND i7.SessionID IN (
SELECT i5.SessionID
FROM tbl_Items i5 (NOLOCK)
WHERE
i5.status <> 11
AND i5.referenceid = @referenceid
AND i5.itemid IN (
SELECT MAX(i6.itemid)
FROM tbl_Items i6 (NOLOCK)
WHERE
i6.referenceid = @referenceid
AND i6.status IN (7,11,8)
GROUP BY i6.sessionid
)
)
GROUP BY i7.SessionID
)
)

GROUP BY i2.sessionid

we know this query is pretty bad and can be optimized. however, if we run this query as is on 2005 it takes about 2 hours to run...if we run the exact same query on 2000 it takes 9 seconds.

so this query on 2005 if run takes 2 hours..however, if we omit the s.IsInternalStatus = 0 or the i2.referenceid = @referenceid line it takes about 9 seconds.

why would this be? it makes no sense why omitting one of those where clauses would increase the performance of the query by 2 hours? we know its a bad query...but this doesnt make sense.

any one else run into this problem?