É apenas uma única mesa? Tem certeza de que seu sistema não pode exportar como csv? (Parece incomum que possa exportar para o Excel, ou html, mas não csv.)
Eu ficaria tentado a dividir o arquivo (novamente) e depois montá-lo novamente. Eu tentaria substituir (em ST ou outro editor) texto em primeiro lugar que não requer regex. A regex-substituição é provavelmente muito mais lenta que a substituição padrão. Eu usaria o padrão de substituição, tanto quanto possível, mesmo usando-o apenas para reduzir a quantidade de substituições de expressão regular que preciso fazer. Eu experimentaria um pouco para descobrir quanto tempo o processo inteiro levaria.
Como alternativa, posso tentar converter o arquivo para o formato XML, adicionando tags no início e, novamente, substituindo um pouco. Então pule o Excel completamente e eu achei isso para o MySQL:
LOAD XML LOCAL INFILE '/pathtofile/file.xml'
INTO TABLE my_tablename(personal_number, firstname, ...);
para importar XML. "LOAD XML INFILE está disponível no MySQL 5.2"
Você pode esperar para ver se alguém pode contribuir. Boa sorte.