Eu sugiro que você, se possível, primeiro faça uma imagem de disco e só então tente uma ferramenta de recuperação. Isso é para permitir várias tentativas sem arriscar muito (você já fez!).
Pessoalmente, prefiro usar safecopy para criar essa imagem de disco. Não é mais lento que o usual dd , mas também pode tentar várias estratégias caso o disco tenha falhas de hardware. Os arquivos de imagem de disco permitem diferentes tentativas de recuperação, mesmo as mais destrutivas.
Então, em casos como o seu, eu daria uma chance ao foremost , pois ele pode tentar uma recuperação automática do que estiver disponível nessa imagem de disco.
testdisk também é uma boa ferramenta, mas com diferentes objetivos e recursos.
Quanto menor a operação realizada nesse disco após o formato, maiores as chances de recuperar quase todos os arquivos.
Sugiro que você siga o testdisk wiki para realizar a recuperação.