And a follow up question: would the current best way to handle this be to "mark records as deletable" and then do the batched deletion operations when convenient?

Create a column called MarkedForDeletion. Create a job that starts in the off hours to detect how many locks are present on the table, if low then delete X records. Else wait for Y minutes. Put this in a loop. If error detected, breakout of the loop.