Switch traceflag 1222 on. That will result in a deadlock graph been written to the error log every time a deadlock occurs. Post the result of that graph here.
DBCC TRACEON(1222,-1)
Please also post all index definitions.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability