Good idea, but there is still the danger in the "forest" situation that potential legit slots would be disqualified because they are temporarily on the opposite site of a tree.

There needs to be a way for the leader or followers to determine if an obstacle is a temporary (and thus tolerable) situation or if it is truly going to cause a problem.

Think about this: When walking through a forest, for example, or past another interposing object of some sort, if we know where the leader is going, we can realize that, despite being seperated for a brief period, we will soon be rejoined (via direct LOS) in a moment - therefore, we persist as if we were not separated at all. To model this would entail not just an idea of where our leader is at the moment but also a concept of where that leader is going and therefore our own future relative location.

Our questions become:

Is that future relative location a valid one?
Is it accessible from here?

Ultimately the OP has to decide if they want to handle the failure when it occurs or avoid it before it occurs.

Handling it is a matter of each blocked unit backtracking to the closest state at which a valid path can be found (the same paradigm as backtracking up a search tree when you find a dead leaf). Avoiding it requires prediction (reasoning about actions/plans/behaviours) and a means of assessing whether each unit should carry on with what it is doing or change its behaviour. My earlier suggestion was in this vein, but only one unit did the reasoning (the leader) and commanded the others to change. This is one of the simplest means of doing this (and almost certainly not likely to be the best in all situations).

Steadtler: Obviously, how you reform is a matter of assessing the requirements of the situation. If you're in a forest, the leader could simply say, "I'm heading in this direction at this speed as best I can. You do your best to maintain a parallel trajectory" and then each unit manages themselves until told otherwise. This is a perfect situation for switching between steering behaviours that are primarily designed to maintain formation and those that are primarily designed to get the unit to the goal. Think of a subsumption architecture for this. Combine 'stay in formation' behaviours with 'move to goal' behaviours. When you find lots of objects that are making it hard to stay in formation, relax that behaviour and give more weight to 'move to goal' behaviours.

Timkin brings up a great point: Why one architecture to solve all contingencies? Certainly a macro-state over this issue can be used to set what sort of approach you will need to use at any one time. All it takes, then, is a diagnostic analysis of the environment to see which state you are in (as a leader) and give an entire set (or type) of orders accordingly.

Sometimes if you can't solve the problem, you need to back up one layer of assumptions.

A neat trick to use whenever doing any sort of formation movement based on a formation of distance-based offsets: use pathfinding to validate that the spot is roughly the same distance to walk to as it is to fly to in a straight line. Do a search with a node count limit related to the square of the distance (A* search node count is sort of an area, so the relationship to distance is ^2). If your search succeeds, use the spot. If your search fails, a really good fallback spot is the nearest point to the goal you reached in your search (the lowest H point touched that isn't occupied). This worked really well for us in Company of Heroes, since guys can go on the opposite side of very small obstacles like trees/dead vehicles, but they won't go on the opposite side of large obstacles like long walls.

Cheers,
Chris