A failed strategic search means the bots have attempted to go from point a to point b (ie, between where they are now and the orderposition in the strategic area they believe they should be able to reach) but can't find a valid path.
There does not need to be anything wrong with the pathmaps in the sense that they can be good, uncorrupted maps, there just need to be enclosed areas that bots believe they should be able to leave and can't. This is one thing that will throw the error. The trapped bots in caen are on a valid position, the door to the building just isn't pathed in. So it doesn't throw a pathfinding error, just the search error.
Yes, the StrategicAreas are involved, because in conjunction with the pathfinding they form the strategic map the AI is talking (yelling?) about.
I've seen things work once then not again. Try creating a few new sets of pathmaps or running with all black pathmaps. If the bots move, you've probably got blocked paths. If they still don't work with black maps, either your aipathfinding.con file has errors or your strategicareas have errors. Check over both and (if necessary) write a simpler strategicarea set.
If none of that works, try rewriting your strategies.
Some map formulations just simply don't work, even though they should. I have no idea why. AI bugs - as in the real ones, the engine idiosyncrasies - are difficult to spot and there's not usually anything you can do about it except try and avoid the problem.
The main reason bots don't like crossing the bridge in Caen is that they can usually see enemy targets and all in all would rather shoot than advance. That and the LOD bug which drops them in the water if the player is more than about 500m away.
The CP setup in Caen is not really very good for bots. Vehicles for starters can't get to nearly all of the CPs that are actually in the town, and I had to change the staticobjects for the level to even get them to go to the church and park on foot. The vehicles are in much more trouble, they certainly can't get to any of the SAs in town other than the bridge checkpoint.
I really should redo Caen. I know how to avoid most of these issues now, but it'll be a hellishly complex AI to do it. Oh, and cos that one doorway has been annoying me for years...