Deadlocking in cfclient cookie database

Hello, we're running CF mx 7.0.2 and am storing all of our client variables in a cfclient database on SQL Server 2005 SP1. We get about a dozen deadlocks a day on the cflcient database and occassionally a long spurt of deadlocks that basically make our web servers non-responsive from a user perspective. I'm interested if everyone has experience and what strategies they've used to combat this. Some interesting points:

1) Three web servers sharing single cookie database, however, purge is enabled on only one of them. 2 hour purge interval of cookies older than 24 hours. No correlation between purge events and deadlocks.
2) I noticed the two tables CFData and CFGlobal are heaps without clustered indexes. This is a big no-no in my book and heap tables are commonly a source of deadlocks due to SQL server locking mechanism.
3) We do use iframes in our web page so it is possible/likely multiple hits/lookup on cookes per user event.
4) I saw CF has some deadlocking issues with 6.1 and have provided patches but we are running 7.0.2

One thought I had was to change the indexing scheme on the tables and introduce an identity column and clustered index. And perhaps a nightly reindex (index rebuild) to keep it clean.