Ext3 faz hash em nomes de arquivos / dir.
Com tantos arquivos em um diretório, eu não ficaria surpreso se você estivesse executando problemas de colisão de hash.
Ter todos os nomes de arquivos do mesmo tamanho e ter a mesma estrutura torna a probabilidade de uma colisão ainda pior.
Se houver uma colisão, o nome do arquivo será efetivamente inutilizável, como você percebeu.
Eu não tenho mais experiência com esse tipo de coisa, então não posso lhe dar nenhum conselho mais detalhado.
(Nós nos deparamos com um problema semelhante no escritório uma vez e o guru Linux residente usou alguns tunefs mágicos para fazer o problema desaparecer. Eu nunca tive os detalhes exatos do que ele fez. Só que isso tinha a ver com colisões de hash nos nomes dos arquivos .)
Você pode aparentemente definir o comportamento de hashing via tunefs. Existe também uma extensão ext3 chamada "dirindex" que ajuda a lidar com diretórios contendo tantos arquivos.