We once had a similar problem, where we had to delete primary and child data for certain records in a batch process. The solution worked rather well -- mark the primary table with a ToBeDeleted flag, then set up a batch job. The batch job would run once per minute, and it was designed to delete and commit the TOP 10000 rows from the child tables joined to the primary table rows where the ToBeDeleted flag was set. After the batch job had run for a few iterations, the ROWCOUNT would equal zero, which was the condition to delete the primary rows.
Purging thus became a background process, with the load spread across many CPU cycles, not unlike garbage collection in a managed programming environment.