Whilst on the subject of deadlocks, here is a cool way to capture a deadlock, and extract more information from it, other than a SPID and an obiturary! Note the use of the ROLLBACK in the error handler, this is present because the TRY/CATCH statement prevents the victim being killed, without it, you'll have a hung transaction.
BEGIN TRANSACTION
BEGIN TRY
EXEC spProcedure
COMMIT
END TRY
BEGIN CATCH
SELECT
ERROR_NUMBER() AS ErrorNumber,
ERROR_SEVERITY() as ErrorSeverity,
ERROR_STATE() as ErrorState,
ERROR_PROCEDURE as ErrorProcedure,
ERROR_LINE as ErrorLineNumber,
ERROR_MESSAGE as ErrorMessage
ROLLBACK
END CATCH;
You could also have the transaction retry after a WAITFOR if it wasnt time critical, and the timeout on your application is set accordingly; then if it really does fail a second time, actually let it fail.