O comando find
retorna arquivos na ordem dos diretórios. A ordem de diretório não é estável; em alguns sistemas de arquivos, se você adicionar ou remover um arquivo, isso pode afetar a ordem de outros arquivos no mesmo diretório.
Eu questiono sua afirmação de que o tipo não é uma opção. A menos que o processamento de cada arquivo seja extremamente rápido, construir a lista de arquivos é bem rápido. Salve-o em um arquivo para que ele possa ser reutilizado se o trabalho for interrompido.
Você precisa saber de onde parou e voltar de lá. Retomar a partir de uma lista de arquivos já gerada será mais fácil do que resumir algumas enumerações complexas no meio.