Data Rescue é o programa de recuperação de dados mais eficiente que usei no Mac. Eles estão até a versão 3 agora. Eu usei a versão 2 há alguns anos para recuperar com sucesso quase 20 GB de arquivos de música que eu havia perdido.
A única ressalva (e isso pode ser verdade para a maioria dos programas de recuperação de dados) é que, com o Data Rescue, seus arquivos recuperados não manterão seus nomes de arquivos originais. Você obterá uma lista de nomes serializados (por exemplo: file000.mp4, file001.mp4, file002.mp4) e cabe a você descobrir qual arquivo é qual. No meu caso, isso não foi um problema graças ao iTunes - que descobriu como renomear os arquivos observando os metadados de cada arquivo.
Boa sorte.