Are you doing visibility checking (like line of sight) frequently between objects (to see if they can shoot at each other or other ranged interactions) and their enemies/targets?
If so, you can down grade any constant RE-pathfinding to a lower frequency when the target is out of view (you cant be sure where the target is so you are doing more an approximation until you can determine its position again). You would crank it back up when you are closer - but lack of visibility still will effect the raw pathfinding in some way and you would have some searching behaviors or somesuch in the non-visible cases.
The less frequent (rougher) pathfinding also might be used when the target is at sufficient )far) distance.
You might want to look into hierarchical pathfinding which allows pathfinding at a Coarser level and then with a more limited area (to be in your candidate lists) when you are pathfinding in Finer (full) detail.