Aqui pra mim os endereços abaixo dão esse problema, e os demais estados não. (Peguei apenas um endereço de cadas estado)
https://nfe.sefa.pr.gov.br/nfe/NFeAutorizacao4?wsdl
https://nfe.sefaz.ms.gov.br/ws/NFeAutorizacao4
https://nfe.fazenda.mg.gov.br/nfe2/services/NFeAutorizacao4
https://nfe.sefaz.go.gov.br/nfe/services/NFeAutorizacao4?wsdl
E o que notei que tem em comum é que eles possuem o certificado delas foi emitido pela "AC Certsign Multipla SSL".
No paraná por exemplo em produção dá o erro, mas em homologação não.