Deadlock on Insert/Update

Using SQL Server 2008 R2:

I'm currently attempting to track down the cause of a deadlock issue we have. Not sure where to turn. Here's the setup.

TABLE Scores:
id INT IDENTITY(1,1),
first_name VARCHAR(50),
last_name VARCHAR(50),
player_id VARCHAR(50),
score INT

PRIMARY KEY/CLUSTERED INDEX: 
id

NON-CLUSTERED INDEX:
first_name, last_name INCLUDES id, player_id, score

A multi-threaded application processes messages, then calls one of two stored procedures for every message.

If the application has not processed the user, it will call a stored procedure that inserts a row into the table.

If the application has processed the user, it will update any or all of first_name, last_name, scores, based on first_name and last_name player_id does not change.

There will be only one row in the table per player_id.

The thread that the application processes messages is chosen based on the player_id, so two threads will NOT process messages for the same player at the same time.

The INSERT and UPDATE statements are using the WITH (ROWLOCK) directive.

Here's the issue:

The process is causing deadlocks with thread 1 locking the primary clustered index and thread 2 locking the non-clustered index.

I do not understand why the locks are occurring - the UPDATE and INSERT statements are using row locks, and it's been tested and proven that threads are not accessing the same rows.

What could I do to fix this issue?

Caveats:

There must exist two stored procedures, one updating and one inserting. As much as I would like to switch to a single MERGE, that's not gonna happen. : /

Updating any of the NC index keys is an update that has potential to deadlock. This is the typical read-write deadlock due to different access paths. Even if you update different keys, that doesn't eliminate conflicts because the locks are on key hashes, see %%lockres%% collision probability magic marker: 16,777,215. However, you describe the problem as appearing 'immediately' which strongly suggest that some other factors are at play, and we can only speculate about in lack of actual information.

Of course it would be much more useful to capture the deadlock graph and post it here. Discussing on a mere description of the deadlock has only limited value, as your description may or may not be factual, your understanding may or may not be correct and our interpretation may or may not be accurate.

StackExchange Database Administrators Q#14022, answer score: 5