Eu encontrei a solução! O problema foi causado porque eu estava criando a pasta pai do arquivo usando a função php mkdir. Essa pasta estava criando com a permissão 755, independentemente do que eu usei como um segundo parâmetro para a função mkdir. A solução é adicionar duas linhas mágicas antes e depois da função mkdir, assim:
$old_mask = umask(0);
mkdir($folder);
umask($old_mask);
Eu não sei exatamente o que eles fazem, mas funciona agora. A pasta pai tem permissão 777 e eu posso deletar qualquer arquivo dentro dela.