Ah, I see you are using Microsoft SQL Server 7.0. All I can think is that you should open a case with tech support...and perhaps trace activity in the database services to see what is happening when the deadlock occurs. The trace flag you need to activate for DBSession partitions is trc:cr:7:4, which will trace all database service operations.
When a client connects to the process engine and creates a new session, and state logging is active for the engine, then session info is inserted into the WFSession and WFSessionRoles tables. When the session is terminated, then the rows are deleted from the tables.
The tables are accessed in the same order during session creation and deletion, so it is hard to see how a deadlock can happen. We always access WFSession before WFSessionRoles, and they are both keyed by Session Identifier.
Ron's question is a good one. What database product are you using?