Excessive Maintenance ?

Help !!
I am running a database of 500-600mb 20-30% of which is new data daily (5 day old data being deleted as part of the nightly maintenance) And my nightly maintenance is regularly taking an hour plus.
CheckDB, New Alloc, Catalog, re-indexing and dumps are performed nightly (2am ish) and as the system is in constant use I cannot afford such a long task. I can't use weekly dumps/checkDB as we use transaction log replication and these are dumped every minute. I really need some suggestions on how I can improve matters. The deletion of old data in particular is taking a long time due to the use local variables but is there a faster way to do this :

OPEN tnames_cursor
FETCH NEXT FROM tnames_cursor INTO @connectionid
WHILE (@@fetch_status <> -1)
BEGIN
IF (@@fetch_status <> -2)
BEGIN
Select @dRent = DeliveredRetention from ControlDB..connectiontable
where ControlDB..connectiontable.Cid = @connectionid
Delete from MyDB..Table where Cid = @cid
and DateDelivered != NULL
and Datediff(hh,MyDB..Table.DateDelivered,getdate()) >= (@dRent*24)
END
FETCH NEXT FROM tnames_cursor INTO @connectionid
END
DEALLOCATE tnames_cursor
GO

These jobs have also started running out of locks and deadlocking on occaision which seems odd as the system has 10000 available (escalating at 2000)
Any Suggestions would be very much appreciated

Damon