you do not need to format. the recovery cd holds an image of a partition. when you restore the image the partition table and FAT tables are overwritten (also whatever NTFS uses, obviously not FAT). this is essentailly the same as formatting. it works in the same manner as symantec norton ghost or powerquest drive image. in fact many restore CD use ghost.
taken from symantec.com:
the cloning process overwrote the partition table and file allocation tables (FATs) on the source drive, but did not overwrite the data.
The partition table and FAT tables are like a map that tells the computer where to find the pieces of a file. Without the map, DOS and Windows cannot locate the file and the data is unrecoverable. If you can recover the partition table and part or all of the FAT, you might be able to recover part or all of the data.
Data recovery services specialize in recovering data from overwritten and damaged drives. If the destination drive was empty, a data recovery service might be able to recover part or all of your data. If you decide to use a data recovery service, do not use other recovery methods before sending the drive to a data recovery service.