{EDIT} Please ignore the following. I can't find the article where I saw this and I haven't been able to reproduce it in code. I have to retract this assertion.

I'll also add that some of the ad-hoc code that appears in the deadlock graph would concern me. Consider the following lines from the deadlock graph....

<inputbuf>

(@P0 [font="Arial Black"]varchar(8000)[/font],@P1 [font="Arial Black"]varchar(8000)[/font])select token, type, value from cache where token=@P0 and type=@P1 </inputbuf>

<inputbuf>

(@P0 [font="Arial Black"]varchar(8000)[/font],@P1 [font="Arial Black"]varchar(8000)[/font])delete cache where token=@P0 and type=@P1

</inputbuf>

Now, let's look at the definition of the table...

CREATE TABLE [dbo].[cache](

[token] [font="Arial Black"][char](36)[/font] NULL,

[type][font="Arial Black"] [varchar](50)[/font] NOT NULL,

[value] [nvarchar](max) NOT NULL,

[cacheTime] [datetime] NULL

) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

CREATE NONCLUSTERED INDEX [IND_cache_token_type] ON [dbo].[cache]

(

[token] ASC,

[type] ASC

)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

GO

Do you see any disparity between the ad-hoc code data-types and the table data-types that just might cause some unnecessary implicit conversions?