It also happens deterministically for me. I tried basically all the combinations of checkboxes in the options and after each game load, I have no borders (even in cloth map). Given that city borders have a gameplay influence (where your settlers can do their job), this is a bit more than a minor bug.
Stardock, this is *not* how you are supposed to incite us to play Ironman mode!
(OTOH, in cloth map, it could be nice to have our empires fully shaded, like the minimap does, instead of just the border drawn...).