Would have to see your typical queries to be sure, but it's extremely likely the clustering keys are backwards, i.e., they should be ( timestamp, ident ) rather than vice versa. But that's almost impossible to fix/change now. Maybe you can get downtime on Christmas Day? (Not a joke, that's when I do a lot of my "table can't be down" maintenance.)

You can REORGANIZE the index, as that's always done online and in relatively small chunks. Still, make sure you have several gig of pre-allocated but unused log space available.

Also, you can put your data into the bold parts of the script below and then it to check existing index usage.

So the DELETEs are not of contiguous blocks of old rows, but instead some rows are deleted and some are not?

USE [<your_db_name>]

SET DEADLOCK_PRIORITY LOW --probably irrelevant, but just in case

DECLARE @table_name_pattern sysname

SET @table_name_pattern = 'your_table_name'

PRINT 'Started @ ' + CONVERT(varchar(30), GETDATE(), 120)

-- list index usage stats (seeks, scans, etc.)

SELECT

ius2.row_num, DB_NAME() AS db_name,

CASE WHEN i.name LIKE ca2.table_name + '%'

THEN '~' + SUBSTRING(i.name, LEN(ca2.table_name) + 1 +

CASE WHEN SUBSTRING(i.name, LEN(ca2.table_name) + 1, 1) = '_' THEN

CASE WHEN SUBSTRING(i.name, LEN(ca2.table_name) + 2, 1) = '_' THEN 2 ELSE 1 END

ELSE 0 END, 200)

ELSE i.name END AS index_name,

CASE WHEN i.is_unique = 0 THEN 'N' ELSE 'Y' END + '.' +

CASE WHEN i.is_primary_key = 0 AND i.is_unique_constraint = 0 THEN 'N' ELSE 'Y' END AS [uniq?],

ca2.table_name,

i.index_id, --ius.user_seeks + ius.user_scans AS total_reads,

dps.row_count,

SUBSTRING(key_cols, 3, 8000) AS key_cols, SUBSTRING(nonkey_cols, 3, 8000) AS nonkey_cols,

ius.user_seeks, ius.user_scans, ius.user_lookups, ius.user_updates,

ius.last_user_seek, ius.last_user_scan, ius.last_user_lookup, ius.last_user_update,

fk.Reference_Count AS fk_ref_count,

DATEDIFF(DAY, CASE WHEN o.create_date > ca1.sql_startup_date THEN o.create_date

ELSE ca1.sql_startup_date END, GETDATE()) AS max_days_active,

FILEGROUP_NAME(i.data_space_id) AS filegroup_name,

ius.system_seeks, ius.system_scans, ius.system_lookups, ius.system_updates,

ius.last_system_seek, ius.last_system_scan, ius.last_system_lookup, ius.last_system_update

FROM sys.indexes i WITH (NOLOCK)

INNER JOIN sys.objects o WITH (NOLOCK) ON

o.object_id = i.object_id

CROSS JOIN (

SELECT create_date AS sql_startup_date FROM sys.databases WHERE name = 'tempdb'

) AS ca1

CROSS APPLY (

SELECT OBJECT_NAME(i.object_id/*, DB_ID()*/) AS table_name

) AS ca2

OUTER APPLY (

SELECT

', ' + COL_NAME(object_id, ic.column_id)

FROM sys.index_columns ic

WHERE

ic.key_ordinal > 0 AND

ic.object_id = i.object_id AND

ic.index_id = i.index_id

ORDER BY

ic.key_ordinal

FOR XML PATH('')

) AS key_cols (key_cols)

OUTER APPLY (

SELECT

', ' + COL_NAME(object_id, ic.column_id)

FROM sys.index_columns ic

WHERE

ic.key_ordinal = 0 AND

ic.object_id = i.object_id AND

ic.index_id = i.index_id

ORDER BY

COL_NAME(object_id, ic.column_id)

FOR XML PATH('')

) AS nonkey_cols (nonkey_cols)

LEFT OUTER JOIN sys.dm_db_partition_stats dps WITH (NOLOCK) ON

dps.object_id = i.object_id AND

dps.index_id = i.index_id

LEFT OUTER JOIN sys.dm_db_index_usage_stats ius WITH (NOLOCK) ON

ius.database_id = DB_ID() AND

ius.object_id = i.object_id AND

ius.index_id = i.index_id

LEFT OUTER JOIN (

SELECT

database_id, object_id, MAX(user_scans) AS user_scans,

ROW_NUMBER() OVER (ORDER BY MAX(user_scans) DESC) AS row_num --user_scans|user_seeks+user_scans

FROM sys.dm_db_index_usage_stats WITH (NOLOCK)

WHERE

database_id = DB_ID()

--AND index_id > 0

GROUP BY

database_id, object_id

) AS ius2 ON

ius2.database_id = DB_ID() AND

ius2.object_id = i.object_id

LEFT OUTER JOIN (

SELECT

referenced_object_id, COUNT(*) AS Reference_Count

FROM sys.foreign_keys

WHERE

is_disabled = 0

GROUP BY

referenced_object_id

) AS fk ON

fk.referenced_object_id = i.object_id

WHERE

i.object_id > 100 AND

i.is_hypothetical = 0 AND

i.type IN (0, 1, 2) AND

o.type NOT IN ( 'IF', 'IT', 'TF', 'TT' ) AND

(

o.name LIKE @table_name_pattern AND

o.name NOT LIKE 'dtprop%' AND

o.name NOT LIKE 'filestream[_]' AND

o.name NOT LIKE 'MSpeer%' AND

o.name NOT LIKE 'MSpub%' AND

--o.name NOT LIKE 'queue[_]%' AND

o.name NOT LIKE 'sys%'

)

--AND OBJECT_NAME(i.object_id /*, DB_ID()*/) IN ('tbl1', 'tbl2', 'tbl3')

ORDER BY

--row_count DESC,

--ius.user_scans DESC,

--ius2.row_num, --user_scans&|user_seeks

db_name, table_name,

-- list clustered index first, if any, then other index(es)

CASE WHEN i.index_id IN (0, 1) THEN 1 ELSE 2 END,

key_cols

PRINT 'Ended @ ' + CONVERT(varchar(30), GETDATE(), 120)