Here in Minneapolis Minnesota, the data recovery services Kroll Ontrack
http://www.krollontrack.com/ are headquartered here. Their company does a lot of different things other then data recovery, but their data recovery services DO cost an assload of money.
When the shuttle columbia burned up, NASA recovered some 6gb or something seagate drives and they brought them to kroll and were able to pull a 90+% recovery rate off those drives. I don't have a source on this, but im sure a simple google search would find it.
However the above wasn't data that was overwritten, just burned and partially melted. Also as for your questions, it widely depends on a multitude of factors. Sometimes you can pull most all of it, and sometimes you just can't.