After even more investigation :)
RepositoryService::deleteDeploymentCascade() doesn't seem to cascade down to process instances any longer.
This, however, works:
List<ProcessDefinition> deployments = repositoryService.createProcessDefinitionQuery().processDefinitionKey(key).list();
for (int i = 0; i < deployments.size(); i++) {
ProcessDefinition pd = deployments.get(i);
List<ProcessInstance> processes = executionService.createProcessInstanceQuery().processDefinitionId(pd.getDeploymentId()).list();
for (int j = 0; j < processes.size(); j++) {
ProcessInstance processInstance = processes.get(i);
executionService.deleteProcessInstanceCascade(processInstance.getId());
}
}