You "format" a hard disk to make it usable by some operating system. To do this, all that is needed is that the hard disk space is initialised with the appropriate index areas - be they inodes, MFT, what have you.
The very nature of a file system demands that for efficiency's sake, these index areas are the smallest possible fraction of the hard disk. You don't want to buy 100 and discover that you can only fit 60 in there.
The precise details of where and how the index area is organized vary with the operating system and the file system type (Windows has NTFS, ExFAT, VFAT and FAT; Linux has ext4, ext3, ext2, btrfs, reiserfs and a host of other types, in addition to its own implementations of NTFS and FATs; Mac OS has HPFS and others; and so on).
But in all cases, you can see that formatting will only affect about 2-5% of the hard disk. Even if the data stored in the remaining 95-98% of the disk is unreachable by normal means, it is still there, and can be read back with special software.
But this is the minimum possible formatting - the so called "quick format". To be really sure that the remaining space is useable, the "complete" format will write (and often re-read and compare) the "data" space. By doing this, the operation will take much longer, and unless the formatter decided to read each sector and rewrite it as it was ("non-destructive format"), just to see whether it receives a write error when 'refreshing' each sector, for all intents and purposes the data is now lost.
How lost is it? Well, a thorough explanation would require reading Gutmann's paper on hard disk data storage and erasure. To keep things simple, let's say data is memorized as strings of binary 0s and 1s. This is what the "external" interface will let you see.
But if you could hop a ride inside the disk, you would see that what is actually read from the spinning platters is an analog signal that goes from a "reference level for 0" to a "reference level for 1", and this is encoded as a magnetic analog signal whose exact parameters depend from the hard drive technology (and references, as well as other finer details, probably depend from the hard disk manufacturer). If the analog signal is below, say, 0.3, the interface will report a 0. If above 0.7, it will report a full 1. If it's in between, it will consider it ambiguous, therefore an error, and try correcting it with several strategies (probably using Reed-Solomon error correction codes intermixed with regular data). If it can't recover the block, then it will report a higher level error; lower level will be hidden and only seen through SMART, if at all.
Data recovery companies will have hardware capable of reading that signal with stricter tolerances, and in this way, a disk whose signal has dropped too far from spec to be readable by consumer hardware will still be recoverable, even easily (usually at a steep price).
Now if you really wanted to recover some formatted data, and money were no objection, you could reason thusly: this disk has been formatted and overwritten with random data. Where now a 1 can be read, I can't know whether there was a 1 before, or instead a 0. Or can I? It turns out that I can. Magnetic materials show hysteresis - they change magnetization with difficulty. This is crucial for HDs, since you don't want any of those 1s and 0s to decide they want to flip while you're using them to store precious data. But it means that they retain traces of the past magnetizations.
So, if the "preexisting" data was a 0, and has been rewritten with a 1, the analog signal you'll get won't be a full 1 - it will be more akin to a 0.9. Similarly, 1s that have become 0s will read as 0.1. Zeroes that kept being zeroes will be 0.0, ones that remained ones will read 1.0 -- and lo and behold, you can read whatever was written on the disk before the format.
Again: this assumes a single pass of overwrite, it assumes using special hardware, knowing how to use it, a lot of time (it's definitely not so cut and dried as I made it look for simplicity's sake), etc.; basically, unless you royally pissed off the NSA, it's not gonna happen, period. Even then, they might believe it possible to recourse to other means of getting the data.
Another source of "past data" is the microscopic wobble that the disk heads undergo while they fly over the magnetic domains that constitute 1s and 0s. The new "track" might overlap the past track by 90%, which is more than enough to call it working, and still a magnetic force microscope could look at the surviving 10% and read it off.
For all these reasons, there are "disk wipers" that write on the disk, using not (only) random data, but data designed to minimize the chances of recovery from hysteresis analysis, electron microscope scanning, and so on. According to a somewhat dated research by Gutmann, this may require up to thirty-five passes of overwrite, after which the disk is proof against anyone except maybe Mentor of Arisia.
To sum it up
- disk reporting "unreadable": perhaps recoverable by specialized hardware
- quick format: data mostly recoverable by an average-skilled user using readily available tools. You quick-format a drive, 98% of your documents are still there for the taking. It only seems they aren't anymore.
- complete format (overwrite 1 pass) or equivalent: data unrecoverable except by terrifyingly expensive and never sure-fire techniques.
- overwrite N passes: recovery unfeasibility rapidly grows from "Kroll Ontrack and several 1000's US$" level to "NSA level" to "alien technology" to "a miracle".
Given the time and hassle involved with a full 35-pass erasure, it would probably be faster to destroy the hard disk.