Sounds like you used packet writing software which is known not to be a reliable backup method. The 20-25 minutes sounds like the drive was actually performing a full format of the discs and not actutally writing files. Next time I would really suggest using a write once medium or backup onto another hdd.
As for recovering data, there are programs out there, some googling will help. I have had limited experience trying to recover data off a reformatted hdd. I think it would also depend on when you installed xp again, did you choose fast format or complete. As I think complete format might zero out the hdd? Someone wanna confirm this?
All I can say is good luck finding a software solution for recovering data. Maybe try reading the discs in another drive? That's about all I could think of.