Ok, graças à ajuda inicial do rzab, redefini sua regra para essa solução de trabalho:
location / {
if ($args ~* "/?param1=val1¶m2=¶m3=[0-9]+¶m4=.+¶m5=[0-9]+") {
rewrite ^ http://www.example.com/newparam/$arg_param3/$arg_param4? last;
}
}
Acabei de adicionar uma condição para evitar a recursão infinita e uma? no final da regra para se livrar dos parâmetros iniciais . Funciona perfeitamente:)