You must wait between several days up to a week in order to delete the parent record. Even if you empty the recycle bin, the records are not "permanently" deleted until some reaper job on the Salesforce side runs to truly delete them.
If you're in a rush, you can open a case with Salesforce asking to "run a physical delete" on your org. They will require that you agree to empty your recycle bin first.
The deleted records don't count toward your data storage limit.
We have worked around this problem by setting a 'status' field on the parent object to indicate that we want it deleted. After we delete all of the child records, we set the status to 'Deleting'. Then, create a Scheduled Apex job that runs around nightly trying to delete the parent records that are in that status. You must rescue the possible exception and carry on. Sooner or later, the records can be deleted.
Last caveat: sometimes the org gets corrupted and even the 1 week rule doesn't hold true. In that case, you will need to open a case and have them escalate it to R&D for physical deletion. This is rare, but it does happen.
The bit of Scheduled Apex we use looks something like:
List<SupremeQueryResult__c> deletedSnapshots = [SELECT Id FROM SupremeQueryResult__c
WHERE Status__c IN('Deleted','Deleting')];
for(SupremeQueryResult__c result : deletedSnapshots){
try{
delete result;
}
catch(System.DmlException dmle){
if(dmle.getDmlType(0) != StatusCode.DELETE_OPERATION_TOO_LARGE){
throw dmle; //reraise
}
}
}
SalesForce themselves have suggested adding in ORDER BY Id as there are certain optimisations built in around the fact that Ids are ordered. The first run after making this change successfully avoided timing out, I will see how it runs over the next few days and mark this as an answer if it's helped.
Best Answer
You can use Dataloader for that, and use the Command Line Interface (CLI). This way, Dataloader can be invoked using the scheduler of your system OS - like Windows Scheduler - to call a batch file that will in turn call the Data Loader.
Through the Dataloader config file, you can automatically login.
To use the Dataloader CLI, you find details here: http://wiki.developerforce.com/page/Using_Data_Loader_from_the_command_line