I will answer my own question because I found a fix for this.
SQL Server database for Moodle should have Is Read Committed Snapshot On option set to True (default value is False). You can do this via SSMS / Database Properties / Options or via T-SQL. Please note that all currently active database connections drop when this is being changed.
As soon as I changed it deadlocks stopped.
How did I find I needed to do this? I was upgrading my test Moodle instance from 2.9.2 to 3.0.10 and during the database upgrade I was given a message about it. I don't have exact wording of the message but it was something to the effect that if I don't do this Moodle may experience errors in high concurrency environment, which is exactly what I was seeing.
The message also provided a link to this page:
https://docs.moodle.org/34/en/Installing_MSSQL_for_PHP#Installation_overview
where more of the database options are recommended to be changed
And this is a similar page for Moodle 2.x:
https://docs.moodle.org/2x/pl/Installing_MSSQL_for_PHP
Unfortunately installer for Moodle 2.9 doesn't warn you about it, so we never changed this option in the beginning.