We do this all the time with DBXL Web Service, which exposes a method for deleting documents.
You could look for a SharePoint Web Service method that deletes documents and if one exists you could write code to call it. Or, you could just install the free trial of DBXL and have it working in under an hour.