Batch convert keeping folder structure

If I'm understanding you correctly, yes, this should be possible. There's an option in the AME General prefs called "Increment output file name if file with same name exists." You'll want to disable this to avoid creating a new file with "_1" appended. 

Do you have a way to easily load all of your files in at once? For jobs like this, on Windows I use Voidtools Everything, which is a fantastic piece of software that (once it indexes your entire drive) instantly pulls up any file. Depending on how your files are organized or named, you could quickly pull a list of the thousands of files and then drag them direclty into AME's Queue panel. This saves you from having to navigate through a bunch of folders and pull them into AME one-by-one. You might not want to try to process thousands of videos at once, but hey, give it a whirl and see if AME crashes or not.

You can drag one file in, choose your desired MP4 preset, then drag the other thousands into the Queue panel. This will automatically set the output location to be the same as the source, and the preset of all queued items wil be the one you just selected. As long as you unchecked the pref I mentioned before, you should be good to go.