Great article on investigating the deadlock. Just a note that if you're running SQL 2005/2008, the trace flag 1222 (http://msdn.microsoft.com/en-us/library/ms178104.aspx) provides a lot more information so you don't have to do quite a much undocumented digging (though I found it very interesting).
Instead of the trace flag, I'd personally recommend setting up WMI to log the deadlock info: http://technet.microsoft.com/en-us/library/ms186385(SQL.90).aspx.
The WMI alerts can actually be a bit more resource intensive and problemattic to setup. There are a number of more moving parts involved with the WMI alerts where as the Trace Flags or a SQL Trace has minimal configuration required. In the end, if you use Trace Flag 1222 in SQL Server 2005/2008, the deadlock graph is the same from WMI, SQL Trace, Profiler, and the Trace Flags.
SQL 2008 offers Extended Events, watch for an upcoming article that I have already submitted which capture deadlock information natively while your server is running. Watch out though, the deadlock information changed to a new format in SQL 2008 that is only output by Extended Events and only Extended Events can capture and display a multi-victim deadlock, which is why there was a change made to the deadlock graph formatting in 2008 from Extended Events.
As I mentioned yesterday, deadlocks aren't necessarily the problem. If your app is coded correctly it can handled the error raised and rerun the statement and it will most likely succeed on the second attempt.
Jonathan Kehayias | Principal Consultant | MCM: SQL Server 2008 My Blog
| MVP ProfileTraining
| Become a SQLskills InsiderTroubleshooting SQL Server: A Guide for Accidental DBAs