Os CEPs brasileiros são formados por um padrão de agrupamento definido pelos Correios.
Este padrão toma como base que o início dos números identifica de qual estado o endereço corresponde.
Tendo essa tabela como referência, é possível verificar se o CEP utilizado numa NFe, tanto para o endereço do Emitente quanto para o endereço do Destinatário estão corretos.
Atualmente, a Sefaz não realiza nenhum tipo de validação em relação a estes campos, contudo, outros problemas (não acusados pela sefaz) podem ser originados por este possível erro no preenchimento, como o envio da mercadoria a um local indevido.

Caso de exemplo:
Caso uma nota seja emitida para um destinatário paranaense, preenchida com o CEP do mesmo igual a 79415-000, um alerta deve ser levantado, pois o dígito inicial 7 corresponde aos estados de Distrito Federal, Goiás, Tocantins, Mato Grosso, Mato Grosso do Sul e Rondônia, conforme tabela abaixo:

Segue a tabela com os estados brasileiros e o primeiro dígito do CEP.