Stored Procedure Deadlock On Self With Subquery

Here's a really weird one for any SQL Server gurus out there...

We have observed (SQL Server 2000) scenarios where a stored procedure
which

(a) begins a transaction
(b) inserts some rows into a table
(c) re-queries another table using a subquery which references the
inserted table (correlated or not)

will deadlock itself at point (c), even when it is the only task on
the server.

[I use the term 'deadlock' because I can't think of anything else
appropriate, even though, as stated, this is the ONLY task executing,
so this isn't a classical deadlock situation]

A typical deadlocking scenario would be (assume insert_table is the
table into which some rows are being inserted)

begin transaction

insert insert_table(col....) select (col....) from some_other_table

/* this following query will deadlock and never complete */

select some_other_table.col
from some_other_table
where not exists (select *
from insert_table
where some_other_table.col = insert_table.col )


Whereas if the offending second query in the sequence is rewritten as
a join

e.g

select some_other_table.col
from some_other_table
left join insert_table
on some_other_table.col = insert_table.col
where insert_table.col is null

the query will not deadlock.

If the subquery is an aggregate function, a deadlock will also not
occur.

If the transaction is committed prior to executing the blocking query,
then it will not block (hardly surprising; if it did, there'd be major
problems with SQL Server!).

Note that this is a canonical case of a much more complex SP, and that
simplified test cases often will not deadlock; you need a significant
amount of data, typically 30,000 rows or more to see the problem. The
blocking query is, in real life, used to drive a subsequent table
insert operation, but this is not relevant to the problem.

We conclude that there is some problem, possibly involving catalogue
contention, if a temporary table must be created in a subquery within
a transaction in a stored procedure, and if the subquery involves
references to a table for which locks have been acquired.

Note that the lock timeout will never trigger and a deadlock victim is
never chosen, presumably because the deadlock occurs entirely within
the same SPID.

Locking hints and transaction isolation level setting does not affect
the result. Note also that the exact same queries, executed as a TSQL
batch, do not deadlock; you must place them in a stored procedure.

Recovery mode for the database is SIMPLE, and the problem is portable
across databases; it can also be exhibited with MSDE/2000, and is
independent of whether or not the database server is the local machine
or not.

Has anyone else experienced this problem and/or know of a workaround,
other than those mentioned here?. It does look awfully like a bug with
SQL Server, since a single task should never be able to deadlock
itself, surely.