Primeiro: PARE DE USAR O DISCO ONDE VOCÊ APAGOU O ARQUIVO e faça todas as operações de recuperação de um Live-CD. Isso evitará que outros aplicativos sobrescrevam o que restar de seu arquivo.
Você pode tentar PhotoRec . Na maioria das vezes, ele deve recuperar pelo menos alguma coisa, mas se os dados antigos já tiverem sido sobrescritos, você estará sem sorte.