Although your primary key is dubious, the datatype and contents are not
the issue. What are your indexes like? If you do not have an index on
the datefield, and your clustered index is on the primary key that
you've identified, then your delete statement is battling some serioud
fragmentation issues.