Yes, you're correct; If the procedure fails, then running it again clears up whatever is left, so I am not worried by the process. I think the business owners are worried really because they want to sell the machines to other people, so if the deletion job fails and has only deleted half the records, then there potentially wouldn't be a DBA to help sort out the issue.

That's a good point about deleting parent child records together. I actually have done it in table order committing after clearing out each table then moving onto the next. I'll change it to do all tables in the batch. That makes much better sense!