No ORDER BY, no guarantee of order. End of story.

It looks like you edited the deadlock graph to take the object and index names out, unfortunately that's made it hard to see what's going on. Can you either edit...

That table just has a 2-column primary key. It's now the designers of the database set it up. It probably shouldn't be  (The SalesOrderDetailID column is unique by itself iirc),...

You really should sort the VM configuration out.

You can 'just' upgrade to Enterprise edition, but 16 cores of Enterprise licenses will be quite a bit more expensive than...

Google for "SQL Server edition hardware limits" and you should get the comparison page (it's what I do any time I need it)

SQL Server in VMs in Azure or Azure SQLDB?

An index will only have an entry in that DMV if it's been used at least once, for anything, since SQL Server last started.

Estimated executions: ~19000, actual executions: 0. In that plan they key lookup is not worth removing as it's not doing anything.
Why you've got such bad estimates for row counts...

No easy way to do that, and you will have to take into account all sorts of conflict problems when you do it.

What happens if a row was...

You mean a backup that only contains data between when it's taken and some previous point in time?
That's a differential backup, but it won't do what you want, as...