There's no mystery: the only way to make data recovery impossible is to overwrite everything. If you only overwrite part of the disk, then anyone who then gets access to the disk can recover those parts you didn't overwrite. It may be more or less difficult to find out how those parts are organized, but files do tend to be in continuous chunks (filesystems tend to try not to fragment files too much, because consecutive reads are faster), and most file formats contain recognizable structures.
If you encrypt the data, then it's enough to overwrite the key. In that case the attacker would only get hold of some unexploitable encrypted data. This is why some mobile devices encrypt their storage with a key that isn't difficult to extract: it makes it more likely that remotely wiping a stolen device will succeed (it only takes one slip from the thief to let the device connect to the network and receive the self-destruct order).
Overwriting the data with zeroes is safe. You'll find a lot of recommendations to overwrite multiple times and with random patterns (“Gutmann wipe”), but this is mostly a legend, stemming from a time when drives were simpler and data could be recovered (with a low success rate) in an electronics lab; see How can I reliably erase all information on a hard drive? and Why is writing zeros (or random data) over a hard drive multiple times better than just doing it once?. On flash drives, this is more complex; see Is it enough to only wipe a flash drive once? and Can wiped SSD data be recovered?