I've only had an issue with this when using ELCP or Custom World Generator mod, are you using either?

I'm using 5 mods.

Necromancers

Middle Earth

Crixler's Palette Expansion

Endless Heroes

Westeros

That's it. I did use a seed I found when looking for a good start for my first game. I restarted because I made a mistake and was a bit bummed I didn't get the same starting location.

I can try removing the mods and restart to see if I have the same problems.

I'm assuming Middle Earth or Westeros, those both affect the map yes?

Only Middle Earth mentions it, but my guess would be so. When I got those two mods, I assumed it would work like in Civ that I would have a custom map to play on if I chose to.

I checked on Steam and both of them do and they both were updated last in 2017 so I removed them. Didn't look at the dates when I subscribed.

you might want to install ELCP, it breaks a lot of mods but it fixes many issues related to this.

Map mods asadly have a bunch of issues, I would generally advise against them.