Olha, se esta na mesma serie e no mesmo ambiente, e vc continua tendo este retorno, é porque realmente estes numeros ja foram inutilizados, acredito ser muito dificil ser algum erro na SEFAZ, pois teriamos uma avalanche de relatos.
No sefaz PArana, para consultar inutilizadas, tem que escolher ano/mês, ja considerou usuario ter feito a inutilização por faixa, acidentalmente de uma faixa grande ? Em anos/meses anteriores ?
Verifica com o contador, considere talvez em usar uma nova serie. Se não for possivel recuperar a sequencia. Isto claro com Supervisão e orientação do contador de seu cliente.