O Windows mantém uma tabela que informa onde seus arquivos de disco são mantidos. Quando você exclui um arquivo, o Windows joga fora a referência, mas os dados ainda estão no disco, mas agora podem ser gravados. Um formato rápido se comporta de maneira semelhante. Quanto mais tempo você continuar a usar uma unidade, as partes mais prováveis dos arquivos serão gravadas. Seu problema é agravado pela reinstalação do Windows que já pode ter destruído seus dados.
Se você formatar uma unidade e quiser recuperar dados, sua melhor opção é desligá-la o mais rápido possível e montá-la em uma segunda máquina como uma unidade que não seja de inicialização e, em seguida, executar o software de recuperação nela. Alternativamente, você pode inicializar usando um live cd e tentar recuperar seus arquivos dessa maneira.