With R-Studio you could open each file as a volume image file (“Open image” button on the “Device view” tab), then scan it with “Extra search for known type files” box checked : this will find anything that corresponds to a pre-defined file type inside those files.
You can do that with Photorec also, which is free : you have to open the program in command line and add the name of a file to open it as a volume image ; or you can right-click on the file and select “Open with”, then search for photorec.exe.
Both softwares let you select which kinds of file types are to be searched ; they have different levels of efficiency, depending on the file type (R-Studio used to be lacking for the correct detection of MKV files, but has improved lately [*], and it recognizes more file types, and seems to better deal with false file signature, with Photorec a legitimate file can be truncated by a false JPG or MP3 file, if those extensions have been checked, I have yet to send a report of my findings to the dedicated forum).
But in any case there's little chance that you will find the videos that you are looking for, and even if only the header had been overwritten it would be very difficult to make the video and audio stream readable again (it can work for MPEG files). I'd be curious to know why Recuva reports them as being in “excellent” state though... (But I've already seen cases where it reported unreliable information regarding file integrity.)
[*] I may have contributed to that :
https://forum.r-tt.com/viewtopic.php?f=13&t=9079