How free-form are the map changes? Do you mean opening and closing doors - or completely changing the terrain as in for example Minecraft?

One option would be to look for strategies that "look intelligent", instead of being perfectly optimal paths at every simulation frame.

Run slow pathfinding for an enemy and store the path. Have them follow the path until they hit a player-created obstacle, and only then re-run pathfinding. Besides being faster, this could let the players use the enemy behaviour to their advantage by creating traps or such.

I'm assuming that changes to any given position X on the map happen much less frequently than pathfinding operations that touch on said position X. Is this the case? If so, then investing the pre-calculation effort (updating the precalc matrix, not re-generating the whole thing) at map update time, limited to only those areas potentially benefiting, might be an effective strategy.

This may be a naive comment (I know very little about pathing), but one thing I've wanted to experiment with is the idea that enemies shouldn't have perfect pathing when the map changes. I always think, why do enemies know how to get from point A to point B? If they have some knowledge of the map, then you can pre-compute paths, but as the terrain gets modified, those paths will be destroyed. It seems to me that it might be more efficient to modify paths, iterating over the changes in the map rather than iterating over each of the enemies. If locations become unavailable, then "dumb" pathing techniques might be reasonable, possibly using some kind of swarming algorithm, or ant-like behaviour to get around local obstacles.