Check out "influence maps" or "potential fields" or "scents" or however they may be called -- google any of those phrases in combination with pathfinding, look at 1-2 videos and you'll grok the idea in a minute, I promise.
They may not solve all your problems or even any of them (hard to tell knowing nothing about your game, after all), but I was absolutely dumbfounded when I played around with them at how cheaply you can get some rather complex (seeming) behaviors (e.g. put the player and some enemies in a maze, give the players a scent that strongly attracts the enemies, but also give them a slight scent that makes them repulse each other, and they'll automagically split up and surround the player).
At the very least, if you're stuck with what you're doing at the moment, play around with those, and maybe you can at least find a use for them that frees up some processing resources for precise path finding where nothing short of it will do.
Have you seen any efficient algorithms that avoid local minima/maxima[0]? All my research leads to either algorithms resembling Dijkstra, or complicated research papers I'm not sure how to implement.
[0] Potential fields can't tell you a route is a dead end until you reach the dead end. Then they only tell you you're at a dead end, but don't tell you how to get out and find a viable route. Add-on exit-a-dead-end algorithms I've seen have very inefficient movement.
Algorithms to avoid the dead end in the first place have to look ahead so far that you might as well use Dijkstra/A*.
You're way ahead of me, I really just dabbled, and I kinda embraced the inefficiency. Though when I did the calculation on the GPU the bottleneck kind of became reading pixels of the texture data for individual agents to make decisions on - otherwise, the potential field updated way faster than the agents could move, and local minima didn't exist long enough to matter. But of course that all really depends on the game map (resolution) and gameplay, and even just having requirements like map sections where some agents don't fit through, while others do, might make it kinda useless.
I think the main power is that potential fields reduce the complexity of the calculation to the map and the number of goals, with an infinite number of agents being able to use that at little cost, but you pretty much always have to build additional pathfinding on top of it. For example, for some games it might be fine for agents to follow the potential field generally, but every tick one of them gets to use Dijkstra/A*, and if that points the other way it follows that path until coming close to another agent or something. Too much efficiency can be off-putting, but also be too predictable and easy to exploit as a player, that's also worth noting. But of course, I'm kind of rationalizing my lack of deeper knowledge here, I'd love to be able to do it perfectly, and then tone that down for realism/gameplay. Alas :)
They may not solve all your problems or even any of them (hard to tell knowing nothing about your game, after all), but I was absolutely dumbfounded when I played around with them at how cheaply you can get some rather complex (seeming) behaviors (e.g. put the player and some enemies in a maze, give the players a scent that strongly attracts the enemies, but also give them a slight scent that makes them repulse each other, and they'll automagically split up and surround the player).
At the very least, if you're stuck with what you're doing at the moment, play around with those, and maybe you can at least find a use for them that frees up some processing resources for precise path finding where nothing short of it will do.