Mark down my vote for a clustered index too - with appropriate fill factor as mentioned. Token is looking VERY much like something that will have values spread throughout the range of characters almost certainly a GUID given the size. If it is, I would start with something like 70% fill factor and run regular maintenance. The problem with HEAP and is you leave pages around that are emptied out to some degree and that space never gets unlinked from the table. The key lookups also cause 2 sets of locks which are likely the primary reason for the deadlocks.