Magentoには時折マイナーバージョンアップの際に意図がよくわからない仕様変更が紛れ込む現象があります。
今回、Magento 2.4.2/2.3.6 で動作検証をしていたところ、タイトルの現象に遭遇しました。
どのようなものか、順番にご説明していきましょう。

Magento 2.4.0/2.3.5-p1での都道府県の並び

まずは次の画面キャプチャをみてください。
これはMagento 2.4.0/2.3.5-p1までの日本語化が適切にできている環境での都道府県の並びです。
標準の動作ではアルファベット順に並ぶのですが、日本の場合はJIS規格で定められている通り、北海道から沖縄に向かって並べるのがセオリーとなっています。

正しい都道府県の並び

Magento 2.4.1/2.3.6での都道府県の並び

では、問題が発生しはじめたバージョンである2.4.1と2.3.6での表示結果を見てみましょう。

正しくない都道府県の並び

一目瞭然ではありますが、なぜか三重県が先頭に来ています。その他の並び順もなんだか奇妙です。
この現象はMagento 2.4.2/2.3.6-p1など最近のバージョンで継続して発生しています。

問題の原因はなにか

問題を発見した当初、「日本語化の実装でなにか不足が出たのだろうか？」と疑いました。
調査したところ、日本語化の実装を外した場合でも現象は発生しました。
さらに調査したところ、Magentoの公式Githubリポジトリの以下のリビジョンで加えられた変更であることがわかりました。

https://github.com/magento/magento2/commit/825cf76921588b546347cffefc4006045aebbd49#diff-8dd1d7fa3a7eb0d299437cc29cecceae2d8b40b6b84e89b515d2a97a6a6a7c99

このリビジョンで変更された下記の部分が原因です。

regionsEntries.sort(function (a, b) {
    return a[1].name > b[1].name ? 1 : -1;
});

JavaScript側で都道府県データを補正する処理が追加されたため、昨年8月4日以降のリビジョンでは都道府県の並びがおかしくなっています。

どう対処すればいいのか

問題のコードが独立した処理として実装されていないため、現時点でこの問題を対処する方法は以下のとおりです。

  1. 導入対象のサイトで使用するテーマに Magento_Checkout/web/js ディレクトリを作成する
  2. region-updater.js を vendor/magento/module-checkout/view/frontend/web/js からコピーする
  3. 前述の問題箇所をコメントにする

とりあえずは上記の手順で対処が可能です。

直る見込みはあるのか

この修正はコミュニティから入ってきたプルリクエストによるものではないようで、おそらくAdobe内部で確認された不具合報告に基づくものだと思われます。
他の国の事情は詳細には把握していないので、日本以外の国で同様の不具合が発生するかは不明ですが、少なくともこの現象が日本向けサイトで問題になる可能性は高いといえます。

すでにAdobe日本法人側には問題を報告済みで、問題の調整に当たられているということなので、将来的なアップデートで修正されるのではないかと思います。
それまでの間は前述の方法で対処するのが良いでしょう。