Asynchronous database inserts from C# always result in a deadlock
Seems like you have issues with your read statement. What is the isolation level on a database?

You can try to get rid of the second read by adding StatusId &lt;2 to the first read statement

(SELECT Id
   FROM dbo.Documents AS d
  WHERE StatusID &lt; 2
   AND EXISTS (SELECT Id FROM @documentData as I
                WHERE i.[File_Name] = d.[File_Name]
                  AND i.File_Size = d.File_Size)
)