Well, Crédit Agricole is kind of a special case, at it was initially for farmers and the like (which do not usually move), and has a heavy reliance on local branches. Although I remember my parents having an account there and not having that issue after moving on the other side of the country.

Yeah a recurring theme in this thread seems to be non french people getting caught in our public service vs private(ised) operator spectrum. As the saying goes "it's not a bug, it's a feature"!

Word of advice from an equally confused native: smile and ask questions. That ought to get you far enough unless you're in Paris (my condolences if you have to deal with the ile de france préfectures or mairies).