Não é necessário canalizar zcat para grep , basta usar zgrep :
zgrep NEW *.gz
Por padrão, quando chamado em vários arquivos, ele imprime o nome do arquivo onde a correspondência é encontrada. (Não será exatamente como sua saída desejada, mas com base na sua pergunta, ela deve atender às suas necessidades.)