Is there freeware out there, that can scan and recover lost files on a NAS disk?
None that I've ever heard of... AFAIK, it's impossible, as the NAS protocols lack the low-level storage BIOS calls needed to be able to access the file system at a low level.
If not, does the WD My Cloud work with a file structure my windows rig will understand, so i can pull the HD out of the cloud device and plug it into my pc and do a recovery that way? Or would i be required to format it before i could get it to work, meaning the cloud device wouldn't recognize it after i plug it back in?
No, Windows does not recognize the EXT4 partition type by default. You'd need to add drivers such as LinuxInternals to allow it to recognize that.
But even then, I doubt the WIndows-based recovery tools would work on anything other than NTFS / FATxx file systems, but your mileage may vary.
If you reformat the whole drive, you've just destroyed the NAS, as that also erases all the operating system and configuration. But it wouldn't do you any good. Even if you reformat the disk, the underlying "erased" partition is still structured as EXT4, so it still wouldn't be recoverable that way.