Considerando que o número de escolhas possíveis para a maior captura é 9, o maior número de movimentos deverá vir de posições sem capturas disponíveis, onde existam tantos reis quanto possível.
Acabei de jogar da posição inicial um jogo em que as brancas conseguiram criar 7 reis, deixando-o 7 * 4 = 28 movimentos legais nesta posição W:B28,K32:WK6,K7,K8,K14,K15,K16,K22.
Se existe uma sequência de movimentos onde o branco cria 8 reis e coloca o 8º rei na casa 23 antes da regra dos 40 movimentos entrar em vigor, então as brancas teriam 8 * 4 = 32 movimentos legais.
Indo ainda mais longe, se o branco criasse 9 ou 10 reis e os colocasse da mesma maneira, exceto para o 9º e o 10º reis em algum lugar na borda, então o branco teria 8 * 4 + 1 * 2 = 34 ou 8 * 4 + 2 * 2 = 36 movimentos legais.
Se eu puder provar que as brancas ou as pretas nunca podem criar mais de 7, 8 ou 9 reis a partir da posição inicial (porque o outro lado é forçado a capturar), então eu teria uma resposta.
36 movimentos parece um limite superior razoável, pois isso significaria que o outro lado capturou apenas 2 peças, o que parece impossível. Mesmo capturar apenas 3 peças parece impossível.
Minha própria resposta não me satisfaz muito, então ainda estou procurando fatos.