Since you're carving in unallocated area, there is a risk that the file was fragmented, and the information about where each fragmented part of the file was stored on the harddrive is no longer available as that was stored in system files from the previous file system.
If this is the case, you need more advanced tools like x-ways, and still with a tool like that, there really isnt any guarentee you can ever recover a fragmented file 100%.
Another thing is that whatever part of an old wallet.dat file you're able to locate, that data can also be partially overwritten by other data.
Recovering files from unallocated area can be tricky if the medium has been overwritten with other data and been used since the time of deletion.
I'll be more than happy to help you, as you get this recovery going, but lower your expectations - I think there need to be some luck involved with the backstory you have told, chances are slim of getting that wallet.dat file recovered fully, but i agree you need to do whatever you can to know if anything is possible.
I have zero experience with the open source softwares mentioned, so how they should be used with regular expressions searches i really don't know