Does anybody have a recommended software solution for this type of problem?
Once I found Photorec, I have not looked back. This tool is the best; it's open source, gets actively developed and has years of maturity.
I can't recommend this tool any more strongly. It is a slightly technical tool which does require a bit of reading up on to use properly, but if you don't mind console apps then go for it. It's not pretty but highly functional.