I once had a pretty bad situation like this. I had a 9gig drive, and didn't know that using full format above the 4gig line wsa a bad idea due to a bug. I did want to format an upper partition, but it looped around and wiped out the lower part of the drive including the RDB information.
I had originally laid out the particions with OS3.1, and my OS3.9 hdtoolbox on a bootable ZIP disk of course used different block size by default. Some fiddling around with a sector editor and a data recovery tool (don't remember the name, it wasn't disksalv but a newer one in an early-ish release) to figure out how file pointers were working to get clues of where the partition boundaries used to be. Couldn't quite get things working right with OS3.9 HDtoolbox, someone mentioned to try the OS3.1 version to get the smaller block size, which seemed to finally work out, and I was able to recover most stuff residing above where format cleaned the disk.
I don't remember how I did some of that anymore, but hopefully I won't have to ever again.
