I don't know anything at all about how rootkits actually work.
But at one time years ago I spent a whole lot of time recovering data for some people and became interested in how hard drives work and data recovery.
We should invite one of the rootkit experts here to comment.
What little I do know about data stored on hard drives tell me that it's impossible for anything to "survive" a proper removal.
If you are able to actually overwrite the entire drive at least once, all the data will be gone and you would not be able to recover anything through software.
Now days with modern drives having the tracks so close together and the tolerance of the drive head so tight and precise, it's becoming extreamly difficult to use an electron microscope as well. Older drives it was possible because the drive head never tracked "exactly" over the old data and the small magnetic regions that were "ouside" the overwritting track could be scanned and therefore you could "read a couple layers down" and find data that was imperfectly overwritten.
However, lets say you overwrite an entire drive. Any virus or rootkit would be gone, simple as that.
I think the myth that a rootkit can survive a format is because people don't understand that a format does not overwrite a drive. A quick format only removes the FAT or MFAT table and the files are left untouched on the drive.
Before Vista, even a "full format" really didn't overwrite the entire drive. It did a quick format and file check and would only overwrite about 20 or 30MB of the drive.
If you ever do a proper overwrite of the drive you'll find that it takes a very long time. Make that a very very long time.
It becomes obvious that all the formats you ever did before really were not doing much.
So I only can think of a couple possible ways that a rootkit can survive a format.
1) The rootkit is in a place that does not get replaced or overwritten (BIOS, MBR, or Boot sector).
2) A quick format was done (not overwritting the actual files, leaving the rootkit on the drive), and the rootkit gets started from something that was not replaced (little grub-like loader in the MBR or boot sector).
For example 2, there is something similar happening in a popular crack for windows. A small hidden loader that starts a BIOS emulation before calling up bootmgr.
Although a rootkit may be able to hide from Windows API's, I know of no windows virus that can also hide from DOS and Linux.
Assuming that the data portion of the drive is completly overwritten and the MBR is replaced, I don't see how anything could survive unless it was small enough to fit in the BIOS and I find that equally hard to believe.
But thats just what I think, I think when people say it can survive a format it's because they don't know how to properly overwrite everything.
Dave