I dropped the existing index and made it clustered with 70% fill factor. We are monitoring the database and I hope we'll see no more deadlocks, I'll post again if this won't help.

Thank you all.