I'm sorry for disturbing your lovely Timbuktu, I hear its mud mosque is pretty neat.
Meanwhile, there are dozens of territories in the game that were not historically peopled in any settled way nor were particularly fertile nor included major trade routes. They only exist because at some point in the game's timeframe, a European power settled it.
However, there is at least one province, Aleut, that was not permanently settled until the 1790s. As far as I know, the game ends in the 18th century, making basically all of Alaska empty, in game terms, anyway. If we can have ahistorical provinces, then, I still don't see why we shouldn't be able to have more of them. I can accept places like in the Himalayas, or the arctic, or interior Greenland, or the deep Sahara or Rub al Khali; But I can't think of a very good reason why most of the western half of North America isn't colonizable, even traversable.