SQL Server Index Update Deadlock
Is there a way to prevent the deadlock while maintaining the same queries?


The deadlock graph shows that this particular deadlock was a conversion deadlock associated with a bookmark lookup (an RID lookup in this case):



As the question notes, the general deadlock risk arises because the queries may obtain incompatible locks on the same resources in different orders. The SELECT query needs to access the index before the table due to the RID lookup, whereas the UPDATE query modifies the table first, then the index.

Eliminating the deadlock requires removing one of the deadlock ingredients. The following are the main options:


Avoid the RID lookup by making the nonclustered index covering. This is probably not practical in your case because the SELECT query returns 26 columns.
Avoid the RID lookup by creating a clustered index. This would involve creating a clustered index on the column Proposal. This is worth considering, though it appears this column is of type uniqueidentifier, which may or may not be a good choice for a clustered index, depending on broader issues.
Avoid taking shared locks when reading by enabling the READ_COMMITTED_SNAPSHOT or SNAPSHOT database options. This would require careful testing, especially with respect to any designed-in blocking behaviours. Trigger code would also require testing to ensure the logic performs correctly.
Avoid taking shared locks when reading by using the READ UNCOMMITTED isolation level for the SELECT query. All the usual caveats apply.
Avoid concurrent execution of the two queries in question by using an exclusive application lock (see sp_getapplock).
Use table lock hints to avoid concurrency. This is a bigger hammer than option 5, as it may affect other queries, not just the two identified in the question.



  Can I somehow take an X-Lock on the index in the update transaction before the update to ensure the table and index access are in the same order


You can try this, by wrapping the update in an explicit transaction and performing a SELECT with an XLOCK hint on the nonclustered index value before the update. This relies on you knowing for certain what the current value in the nonclustered index is, getting the execution plan right, and correctly anticipating all the side-effects of taking this extra lock. It also relies on the locking engine not being smart enough to avoid taking the lock if it is judged to be redundant.

In short, while this is feasible in principle, I do not recommend it. It is too easy to miss something, or to outsmart oneself in creative ways. If you really must avoid these deadlocks (rather than just detecting them and retrying), I would encourage you to look instead at the more general solutions listed above.