No I don't think you need to go in and read/mod with a hex editor or that deep. You have XP and another drive, sounds like you are slaving and digging? Again, not sure what you are doing. If you just lost/had deleted some files from your my documents file then you can still boot your XP?
You can google for "recovery undelete free" and then run some of those programs you find, there are alot out there. Also search these forums for undelete, or recovery, there have been other threads like this and some of them recommend specific programs.
The basic issue with simple recovery is that windows does not actually destroy deleted files, what it does is mark the space as rewritable and removes your access to those deleted files so they no longer are listed(basic explanation). So there are some chances that when you go in and install recovery software on a drive you have a chance of writing into the files you seek. That is why some folks recommend slaving up a drive and running from a different drive.
You say you are using stellar Phoenix and I am not familiar with that stuff but if it is a demo mode/trial it most likely will not recover but only will show you(tease) what is still on your drive. Do not put to much store into crippled demos. If it is the full version call them and get support. If the hex edit the font is specific to their software then it's an odd thing, it should be able to read your stuff without all that.
Here is a link to some free recovery stuff, I use some specific stuff that costs $$ so I really cant help on the freeware stuff, but like I said do some searching here & google. This program looks OK-but really I do not know; it has a small footprint and a filter so you can search for like *.avi or whatever you need. I would run it right from the drive you want to recover from, unless the recovery is very important and you can not chance any loss.
You do not list the specifics to the loss but if it was malicious activity there may be more of a chance that simple recovery will not work.
List more details and I or others will chime in, I'm sure. Good Luck
Edit heres the link
http://www.officerecovery.com/freeundelete/