In one of your replies you wrote:

I'm trying to think of any way to go "up another level", to see the problem from a higher view

Here's a try: You're being given regexes to match against all the filenames in the system, are now looking for a way to optimize that, have discovered some caveats, etc. - maybe you're stuck in the world of string matching? The actual task is searching the filesystem, a task with plenty of existing solutions.

How complex are the regexes you're getting? Do they only make use of simpler regex features like . [] (|) ? * +, or do they use the more powerful features like look-arounds, backreferences, and such?

If the former, then my suggestion would be to parse the regexes and transform them to rules appropriate for a filesystem search. Just one example, if this were some kind of backup tool, you could transform the rules into include/exclude patterns appropriate for rsync.