Você pode encontrar o módulo de mapa para ter um melhor desempenho, especialmente se a maioria das URLs não precisar ser expressões regulares . Por exemplo (não testado):
map $uri $new {
/olddir/part1_de.htm /newdir/sub/category/anotherpage.htm;
~^/olddir/part(?<num>[0-9]+)_en.htm$ /newdir/sub/category/part$num;
...
}
if ($new) {
rewrite ^ $new permanent;
}