Caro, essa situação é complicada.
A empresa pode fazer uma declaração simples informando que a pessoa nunca trabalhou naquele local.
Mas tem que tomar cuidado. Poder ser que algum funcionário desta empresa, esta com o numero de pis desta pessoa que te procurou. Neste caso, cabe as duas empresas a fazer uma pesquisa se o pis desta pessoa consta em algum funcionário no qual trabalha ou já trabalhou nelas.
Tive um caso parecido, mas neste, a funcionária foi dar entrada ao seguro desemprego e constou um vinculo empregaticio com uma empresa que é minha cliente. Fui fazer uma pesquisa nos funcionarios, e um deles estava com o numero de pis desta menina que queria dar entrada no seguro. Neste caso fiz uma RDT alterando o pis do funcionario que estava errado. A menina após alguns dias conseguiu dar seguimento ao processo do seguro...