This problem was finally solved. Timeouts were caused by queries to a large table (> 10GB) with joins to the Users table, running in serializable isolation level.
Of the combination of factors the most important cause of timeouts was the serializable isolation level, without it there would have been just general performance degradation. Debugging was made more difficult by the fact that serializable was set only by another, quite rare transaction, that didn't return the isolation level back to default (read committed), after committing the transaction.
Because debugging this problem had a lot of false starts and "wrong" fixes like upgrading the database server hardware, it might be helpful to recall the right steps that eventually helped to solve the problem.
1. The blocked process report
The key to finding the problem was this excellent blocked process report, using SQL 2012 extended events:
I recommend it to anyone debugging timeouts, I didn't find other tracing tools much helpful.
Blocked process reports showed both blocked queries and blocking queries and the isolation level they are using. You can define a threshold for the wait time, I traced queries waiting for 5 seconds or more. This limited my problem to a single search view in the application, one that runs a SELECT query to a large table (over 1,5M rows and 10GB data) with joins to multiple other tables, including the Users table.
2. Removing joins
Next, I removed the joins from the search query, which helped to eliminate UpdateUser timeouts, but didn't stop blocking when updating the large table itself.
3. Resetting the isolation level
The remaining blocking problems finally tipped me to check the isolation level, which is found in the blocked process report, or in real time by using dm_exec_sessions:
From the real time dm_exec_sessions query I found that some, but not all connections were running in serializable isolation level.
The reason for this, it turned out, was that the isolation level set by .NET SqlCommand is persisted to subsequent commands:
"After a transaction is committed or rolled back, the isolation level of the transaction persists for all subsequent commands that are in autocommit mode (the SQL Server default). This can produce unexpected results, such as an isolation level of REPEATABLE READ persisting and locking other users out of a row. To reset the isolation level to the default (READ COMMITTED), execute the Transact-SQL SET TRANSACTION ISOLATION LEVEL READ COMMITTED statement, or call SqlConnection.BeginTransaction followed immediately by SqlTransaction.Commit."
Finally, I searched the codebase for transactions with non-default isolation levels, and added a resetting commit after each:
SqlTransaction txReset = conn.BeginTransaction(IsolationLevel.ReadCommitted);
txReset.Commit();
With these changes in place, the blocking process report stopped showing any new problems. I let it run for a few weeks before finally stopping the extended event tracing and closing the issue.