Why does this script cause a SQL deadlock often?

I am running a background task within a web job in Azure every hour. Sometimes (it appears to be a little more than 50% of the time, the code will choke (with a deadlock error) on this particular piece of code:

foreach (var ownerToProcess in activeOwnersWithMessageArchiving)
{
    foreach (var extension in extensions)
    {
        using (var db = new SqlConnection(connectionString))
        {
            db.Execute(@"
UPDATE T_MESSAGESTARTER 
   SET Started=@started,Completed=NULL 
 WHERE OwnerId=@ownerId AND ExtensionId=@extensionId;

if @@ROWCOUNT=0
  INSERT INTO T_MESSAGESTARTER (OwnerId,ExtensionId,Started) 
  VALUES (@ownerId,@extensionId,@started)
", new { ownerId = ownerToProcess, extensionId = extension, started = DateTimeOffset.Now });
        }
    }
}

It's a simple update/insert statement. I "believe" I am using row-level blocking too. This is not inside a transaction. Also, there are around 60 ownerToProcess items in the top-level. And each one of those has between 5-60 extension items in the inner loop (in the code above). And that makes for around 4000 executions of this SQL statement throughout each run. Each @owner/@extension combo (in the WHERE clause) is unique.

Sometimes it will run all the way through without errors. But sometimes I will get the deadlock error on one of the executions of the SQL statement. What could be causing this? Is it because I have the UPDATE/INSERT structure in the SQL statement? Or could Dapper be doing something funny?

Another thing to note: the T_MESSAGESTARTER table in question does not have a primary key. Could that be causing this issue?