Post the table design, index definitions and some of the queries that deadlock with each other?
Have you considered snapshot isolation level?
A single table design is bad, but it might be slightly fixable.
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