Do you have more then one processor at this server ? If so, may be the optimizer choose paralelism to resolve the query. If that´s true, try to rewrite the query especifiing the hint (MAXDOP=1). I´ve already have problems with deadlocks in queries that use parelelism for execution, and I solve with this trick. 