No guarantees, but here goes.
First, a .nomedia file is used as a placeholder or as a way for a folder to be hidden from view (in my experience).
As a placeholder, it will make an otherwise empty folder not empty, therefore less likely to be deleted by cleaner apps or other means.
As a way to hide folders, well, that is exactly how the gallery app that I use hides folders that I chose to be hidden.
I have never seen the deletion of a .nomedia file ever result in the loss of any files or folders.
Have you attempted to add the .nomedia file back?
Perhaps this is the answer.
Maybe not, but if something so simple could fix the issue then it is worth a shot.
Next, I would try a different Gallery app, specifically Simple Gallery Pro.
Simple Gallery Pro - Photo Manager & Editor (A premium app for managing and editing your photos, videos, GIFs without ads) -
https://f-droid.org/packages/com.simplemobiletools.gallery.pro
The reasons for this are, well, simple.
It's an excellent gallery that has a feature that will show every compatible image and video on the device.
Also, as it is what I use, I may be of more help if we are using the same gallery app.
Plus, I bet that no matter what, you might like it.
Anyway, back on task, if that gallery doesn't find them with the following:
three dot menu in upper right
show all folder content
then there is a last ditch effort, but it isn't pretty.
There ars a few (if not many) data recovery apps available, of which I have tried only maybe two.
What I discovered was that they will generally only find thumbnails of the original media, and those are very poor quality in comparison.
Also, with those apps you can forget about recovering any video content unless you pay, and there are plenty of unhappy reviews stating that even after payment no videos were found.
The good news is that it is unlikely that the folders are actually gone, unless you deleted them yourself.
Usually there is a multiple step process to ensure that you know that you are sure you want to delete the data.
Simple Gallery goes a step further, adding a 'recycle bin', that allows for files to be restored after deletion for up to 30 days.
Let me/us know if any of this works or helps you out.