Estava com os mesmos "sintomas", sempre que ia consultar geralmente já estava bloqueado, mesmo esperando muito mais que uma hora entre as consultas e sempre consultando a partir do ultimo NSU. Tentei consultar o NSU 0 depois de esperar o "castigo" de 1 hora e nada, sempre bloqueado.
Investigando mais a fundo, descobri que o ERP da empresa também fazia consultas no webservice de distribuicaoDFe. Foi desativar essa funcionalidade do ERP que a consulta no meu sistema voltou a funcionar perfeitamente, usando o mesmo certificado para consultar mais de 10 CNPJs (simultaneamente para cada cnpj, descartando a hipotese do bloqueio ser por certificado).
Ou a sefaz corrigiu o problema exatamente no momento em que estava testando, ou realmente esses problemas são decorrentes de mais de um sistema competindo pelo uso da API, atrapalhando a linearidade do NSU.