Acredito que o webservice da sefaz nao permita esse tipo de consulta que vc quer.
Alias esse procedimento que vc citou de consultar TODA a vez que emitir uma NFe pode te dar problemas por consumo indevido do WS. E ai a sefaz bloqueia qualquer tipo de consumo por um determinado tempo. (e isso é muito ruim pro seu cliente)
O Mais correto, é:
1 - Fazer o tratamento pelo seu software mesmo
2 - se acontecer ainda assim de retornar duplicidade, vc deve tratar essa rejeicao adequadamente. Pode verificar por exemplo se os dados da nota são iguais. Se se, vc avisa o usuario que aquela nota ja foi aprovada, sem necessidade de re-envio. Se for outra nota, entao vc deve reestruturar a numeracao da NFe de modo que não se repita.