Assuming the decision to delete is independent and threadsafe, is it threadsafe to call DeleteOnSubmit in parallel?
All entities will be added to the delete in parallel, then the change will be submitted afterwards.
My testing hasn't shown a problem, but that doesn't inherently mean it's safe....