До боли знакомая проблема
Насколько помню, использовал такие вот проги: EasyRecovery, PowerQuest DataKeeper, Ontrack SystemSuite. Вообще то их походу больше было, но все уже и не вспомню, было давненько уже.

А насчет востановления в спец. центрах, как узнал цену, так и ох**л сразу. От 80 баксов до нескольких штук(с секретной инфой типа). Прикинь, востанавливают даже посыпавшиеся винты.
Но лучше уж самому помудохатся, правда скажу сразу, про медиафайлы, к примеру можеш забыть, хоть и востановит, но чтению они не подлежат.=(

А то что записал парочку файлов, это не беда. Главное, что не всё пространство забил. Так что можеш ещё попробовать, правда уже не всю инфу востановишь.