trial download of file scavenger looks worth trying.
http://www.webattack.com/editorials/e-undelete.html
i backup often, i am just used to windows i guess, i have used partition magic in the past quite a bit, mainly on windows 98 machines, good to get tested once in a while. curious, why did you reinstall xp, and did you delete the partitions when you did the install? this is puzzling to me , why they just disapeared.