Tente adicionar o -depth
flag para processar o conteúdo de cada diretório antes do próprio diretório.
EDIT by Asker: Ou o sinalizador -prune, já que eu não me importo com o conteúdo. Sua sugestão me fez pensar sobre isso pesquisando nos diretórios depois de deletá-los, o que eu não considerei, e me deu a resposta final, então eu queria fazer essa a resposta correta que eu realmente usei.