I'd be willing to bet a dollar it has something to do with those two "NOT IN"s in the query.If you change those to left joins I bet the problem is greatly mitigated, though it won't go away completely.

Deadlocks happen when a depends on b and b depends on a. that usually happens when a query takes a long time to complete. Making the query go fast makes it happen less often because by the time b depends on a, a no longer depends on b.