Passei por situação parecida: foi apresentada certidão negativa, mas fiz a consulta e vi que, no decorrer do certame, positivou. À época, vim aqui pedir ajuda dos “universitários”: veja que houve diferentes entendimentos entre os colegas Emissão de nova certidão, em detrimento da já apresentada - Regularidade fiscal estadual - #9 de Natanael e Emissão de nova certidão, em detrimento da já apresentada - Regularidade fiscal estadual - #10 de Alessandra_Vianna. Depois disso, já aconteceu mais uma vez, com outra empresa. Mas em nenhum dos dois casos foi a trabalhista, e sim a fiscal.
O problema maior é que, de acordo com a Lcp nº 123, art. 43 §1º, o prazo de 5 dias úteis para a EPP se regularizar tem como termo inicial de contagem o momento em que o proponente for declarado vencedor do certame (que, salvo engano, corresponde à adjudicação), o que nos expõe ao risco de depois ter que revogar homologação do certame ou do item, para chamar remanescentes, caso a empresa que se utilizou do benefício não consiga se regularizar.
Sendo assim, em sede de diligência, a proponente ME apresentou comprovantes de que a dívida foi paga ou pelo menos negociada com o ente responsável pela emissão da certidão, como forma de dar maior segurança à Administração de que, em breve, sairia a negativa com efeito de positiva. E, em um dos casos, a referida certidão saiu no último dia da prorrogação do prazo 
, viabilizando a assinatura do contrato.
Não sei como se dão os processos (administrativo e/ou judicial) para reverter a situação de débitos trabalhistas… quanto tempo demora.
Mas, de qualquer forma, acho que não há lastro legal para negar o benefício do art. 43 §1º se a EPP solicitá-lo.