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
}
}
}
