I am thinking of Easeus Partition Recovery, and TESTDISK - there must be several more.
A friend who did some recovery years ago told me that the first sector of a partition ends with 55AA (hex) and shortly before that is a byte string containing FF and FE and the partition type, e.g. 83 for ext3.
He could not remember the details. I presume that the partition finder rescue programs search for these byte strings. And I would guess that a smart program would know what a root directory looks like in NTFS, FAT32, Mac, linux et cetera and also see if that is following any "start sectors" encountered.
Is this how it works?
(I suppose a linux swap partition would contain random crap and be somewhat harder to identify).

well, sort of yes, but a little more complicated when info gets deleted

_________________
Hard Disk Drive, SSD, USB Drive and RAID Data Recovery Specialist in Massachusetts

The following is my favourite resource for MBR, partition table, and boot sector related questions:
http://mirror.href.com/thestarman/asm/mbr/index.html

The author explains, in detail, the structures of the various boot records.

BTW, NTFS maintains a backup boot sector at the end of the partition, and FAT32 has a backup at sector 6. I expect that software such as TestDisk would use these backups to rebuild the primary boot sector and the respective partition table entry.

In fact, here is one example where a user was able to manually repair his NTFS partition using the information in the backup boot sector:
http://www.tomshardware.com/forum/forum ... ost=269210

_________________
A backup a day keeps DR away.

I will concur with that after an experiment: I took a linux disk that was overwritten at the start, many thousands of sectors. I am sure the boot and root partitions would be lost. I tried Easeus and it found the home partition. I expected TESTDISK would do the same, but instead it gave the start and end of a phantom partition 25 GB in size, starting 16 GB from the beginning of the disk. This does not correspond to anything originally on the disk. So perhaps TESTDISK was using what it thought was valid information from the corrupted area?

IMO, if you know how the file system was damaged, then you could assist your data recovery software by undoing as much of the damage as possible. This would involve zeroing the overwritten sectors. By doing this, you eliminate the potential for confusion, as was the case in your test example.

_________________
A backup a day keeps DR away.