exFAT-formatted external drive loses folders
exFAT is not optimal for your situation probably, but unfortunately there isn't really a no-brainer solution for using an external drive frequently with both OS X and Windows, reading/writing large files, and with really low risk of data loss.

exFAT is not a journalled file system, so there is higher probability of data loss than with NTFS or HFS+. exFAT uses a single file allocation table and a single free space map, so there is a higher likelihood of file system corruption due to that (such as if a removable device is disconnected during a write). exFAT does do checksumming that allows it to detect some problems and repair to a consistent state, but that doesn't actually prevent loss of actual data. If it is plugged in and used frequently, that raises the risk that it will be transferring data if a disconnection or power failure happens, which isn't good.

You'd probably be better off going with NTFS - native on Windows and use something like Paragon NTFS in OS X.


https://en.wikipedia.org/wiki/ExFAT
http://arstechnica.com/information-technology/2013/06/review-is-microsofts-new-data-sharing-system-a-cross-platform-savior/
https://discussions.apple.com/thread/4154638


For recovering the missing data and folders (data and with proper directory structure) - there is a good chance they are damaged so it won't be simple if possible. You might be best off babysitting Handbrake some more as you say and recreating the data you need. I might have suggested seeking professional data recovery help, but it sounds like this isn't something critical to you and probably not worth paying for. For example an engineer at a company like ours would have many recovery tools at their disposal and would either try many or know which ones would have the best ability given the situation after some investigating of the damage. Plus they're also experienced. I have seen them recover data from damaged file systems including good file names and directory structure when some software tools are unable to help, because there are actually enough parts of the file table remaining to work from if the tool can do it. 

You could try more software recovery tools, particularly ones that recover specific file types, but it will cost money, and at some point it's just cheaper to go with a data recovery company... and for you, to recreate the data.