Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
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.