色々な本で調べたところ、幸運にも我々は一番早くて簡単な方法を取ったようです。それは
短期滞在の資格で入国
↓
外国人登録を行う。
↓
指定書を入手後(通常は登録申請時に入手可能。)入国管理局に滞在許可の資格変更
(短期滞在から日本人の配偶者等)を行う。
↓
日本人の配偶者等のVISA取得
(通常申請から1ヶ月程度で入手出来ます。)
↓
2週間以内に市役所に変更の届け出を行う
我々の場合は妻がフランス人だったので、短期滞在の場合はVISAが必要無いので比較的簡単に入国出来ましたが、VISAが必要な国であるとたとえ短期滞在であっても色々手続きが複雑なようです。