If I understand correctly, the license_message table has a:
clus index (/PK) on license_message_id
nonclus index on archive_date
<other nonclus indexes>
Yes, the clustering key for this table should be archive_date. Everything you do would likely run faster, often much faster, with the correct clus key. [Technically you could change the existing PK to be non-clus, then change the non-clus index on archive_date to be clus -- that is, change the clus column w/o changing the column that is the "official PK".]
[Again, too many people insist on defaulting the clus key to an identity.]
At any rate, if you must keep the original structure, you can still improve the DELETEs. No reason to do all those joins from the value table back to its parent.
Naturally you can adjust the code below to work in batches, but I would do more than 1000 at a time; try 2,500.
Btw, make sure the log file on the db has existing unused space to log the DELETEs. And a decent autogrow amount (and not a percentage, but a fixed amount). Part, perhaps most, of the reason for the lengthy DELETEs could be log growth.
DECLARE @deleted_ids TABLE (
OUTPUT DELETED.license_message_id INTO @deleted_ids
archive_date < getdate()
INNER JOIN @deleted_ids di ON
v.license_message_id = di.license_message_id
IF @@TRANCOUNT > 0
SQL DBA,SQL Server MVP(07, 08, 09) Prosecutor James Blackburn, in closing argument in the Fatal Vision murders trial: "If in the future, you should cry a tear, cry one for them [the murder victims]. If in the future, you should say a prayer, say one for them. And if in the future, you should light a candle, light one for them."