You could make the enemies and NPC's to find the new path only after certain time has passed.

For 30 fps you could run the pathfinder only after 2 seconds have passed:

Frame 1: find path.
Frames 2...60: move along the path found, checking if hero is next to him.
Frame 61: find new path if hero has moved.
And so on.