Eu encontrei a resposta para o meu problema!
Usando as pistas fornecidas por Allix, abri os arquivos xlsx no 7-Zip e comparei os tamanhos dos arquivos. Havia um arquivo que era muito maior que os outros. O arquivo xl \ drawings \ drawing1.xml era um arquivo que continha várias referências a formatos repetidas vezes.
Passei algumas horas tentando descobrir um padrão, mas não consegui. Nada que eu fosse capaz de fazer funcionaria! Então, depois de um ataque de agravamento, acabei de apagar o maldito arquivo e tentei reabrir no Excel (2010- não o testei no Excel 2007).
Ele reclamou que o arquivo estava danificado e perguntou se eu gostaria de tentar um reparo. Reparar o arquivo simplesmente apagou a forma, mas não alterou a formatação do arquivo. Eu tive que salvar novamente o arquivo como o mesmo arquivo, o que foi um pouco estranho, mas funcionou!
Como eu mencionei antes, eu não tinha testado essa solução para nenhum outro produto além do Excel 2010, então não sei se o arquivo de forma era crítico para o Excel 2k7 ou qualquer produto do OpenOffice. Mas, se você tiver um problema parecido, espero que isso seja útil.