Cleberest.
Se voce formatou, bau bau.
Muito dificil de recuperar.
Até existem softwares especializados nisto, tipo norton utilities, mas é bem complicado, e pode demorar um tempão, e nunca vai ser uma garantia de recuperação total.
Ou usar o comand unformat, só que foi formatado pelo linux.
Não sei , mas parece que não tem solução.
Mas pesquise bem antes de decidir, tudo vai depender da real necessidade de recuperar os arquivos.
É um problemão, que talvez só possa ser resolvido por um especialista em sistemas.
Mas aí voce vai ter que pedir ajuda num site especializado em windows.
O Windows Vista é bem complicado, o meu notebook também veio com ele, e com arquivo de recuperação, que funcionou bem somente duas vezes (não o do cd, mas o do arquivo de recuperação que fica no hd), na terceira vez, deu um pau, que não teve jeito, e a única solução foi reinstalar o Vista pelo cd de recuperação, e os dados (arquivos estavam lá)
O mais importante antes de tudo é ter sempre backup.
O DVD de recuperação deveria funcionar sempre.
Tente de novo, de repente você usou a recuperação de dentro do hd, em vez da recuperação do DVD.
Preste bem atenção nas janelas do ruinwindows, e numa desta pode ser que consiga alguma coisa.
Uma coisa é a recuperação pelo Hd, e outra pelo cd, as vezes entrando pelo cd (DVD), o windows pega o caminho do hd, ou nos confundimos ao selecionar a correta opção.
Para instalar o Ubuntu em dual boot com o vista tive que utilizar a suite da Acronis, para poder resolver os problemas das partições, uma vez que o desfragmentador do windows vista não funciona direito.