Well Ma2t, I do have a few ideas.
You can do a few things here.
However, here is the overall problem. If you use MU, you're going to lose those galleries and directories too, because MU runs off a single set of files. Any user directory or subdomain is virtually created with mod_rewrite.
So the files are still going to be all in one directory, and you still end up with the same problem.
It seems like your main concern is plugins and compatibility. Pardon the term, but if your a "plugin whore", then you may find that many less popular plugins aren't completely MU compatible. You'd have to rewrite parts of them to correct the situation, and some may never fully work.
That being said, I assume your goal is to have less files to maintain and update. Which, either my recommendation for multiple WP sites (without losing anything) or using MU will accomplish this as they are both a single set of files to maintain, a single set of plugins, and a single set of themes.
Back to the problem of having a gallery, in say domain12.tld/gallery/, and in domain6.tld/gallery/ will be an issue with either one.
What "could" possibly be a solution is using Wordpress to map /gallery/ to a specific directory, or "cheating a bit". I've done this with a few programs, and while you have to pay attention, it can work.
Here's a brief overview of this.
Most programs have the capability (whether they say so or not) to move all the files to another directory, but sever from the main address. For example, I can put WP in /wp/, but serve it from /, and nobody is the wiser (with a few minor modifications).
What you could potentially do, is install the gallery into /gallery/user/, and in /gallery/ use an index.php file that simply checks the domain being called as /gallery/, and then include (not redirect to, but as in include_once) /gallery/user/index.php.
The resulting url would be domain.tld/gallery/, but the files are being served from /gallery/user/.
You would of course have to slightly tweak the setting of the install in each /user/ gallery, to make sure it knows it's main domain is domain.tld/gallery/, and not /gallery/user/, as well as that its file path (for includes and such) is /gallery/user/.
The physical url to an image would need to be /gallery/user/ though, but that's a minor detail as most images are pulled as part of a page and not linked to directly.
Then, there is another option, but you will run into a problem with physical image paths and such.
When it comes to galleries, I've only used a hand full. Of those, I've tended to use Coppermine more than anything.
The "best" solution I could think of is something that stores files in the users personal directory or something in WP (modifying the plugin to use path/user_id/ to keep it separate).
But, like I said, either with MU or my multiple domain hack, you're going to have the same problem with any subdirectories. That is, unless there is only 1 domain using that subdirectory, then it would be fine.