I suppose I'm starting to develop a mild if somewhat exasperated affection for SQL Server, but then something like this comes along and annoys me all over again. It's ludicrous to have to go to this amount of trouble to diagnose something as straightforward as a deadlock. On DB2 on the mainframe (what a lot of your readers would regard as 'legacy') the thread which gets chucked out receives an error code (a -911 if my memory serves me correctly) and my all-time favourite error message: "This agent has been selected as the victim of a deadlock", which sounds like an instruction from the CIA But no diagnosis is necessary, nor should it be.
As for how to fix it, it's caused by 2 processes accessing and locking (exclusively) the same data in a different order:
Process 1 has A and is waiting for B. Process 2 has B and is waiting for A. And there they will sit until kingdom come unless the system selects one to kill.
A few things to try:
reduce your lock size - table to page, page to row, and force it to stay there. This has CPU and memory implications, so be careful.
Change your clustering sequence on one of the tables involved (again, look at the bigger picture first).
Ideally, design your apps to access things in the same order. A lot of deadlocks are just the result of bad and inconsistent coding.
If you have a real database hotspot, like a maximum key which gets both read and updated, try adding a very long field to the table, or a very high fill factor, so you only get one row per page. If you are deadlocking at row level, rethink your design.
Dinosaur tricks, but they might work.