It seems like despite the fact we're not using transactions at all we get random deadlock error from SQL Azure.
Are there no transnational situation when SQL Azure can get into a deadlock?
It seems like when we are running a batch of UPDATE queries it acts like the batch is a one big transaction.
All the updates are by id and update a single a line.
There is no such things as "not using transactions". There's always a transaction, wether you start one explicitly or not. Read Tracking down Deadlocks in SQL Database for how to obtain the deadlock graph in SQL Azure. Connect to master
and run:
SELECT * FROM sys.event_log
WHERE database_name like '<your db name>'
AND event_type = 'deadlock';
Then analyze the deadlock graph do understand the cause. Most likely you're doing scan because of missing indexes.