I must assume this has already been discussed?
If not then I would make a few suggestions. We could have Claimed territory, treaty territory, settled territory and defended territory.
Claimed territory is what your explorers basically do, they run around planting a few flags. These have no real effect except that they can lead to treaty territory, where two civs can decide on a mutual border within shared claimed territory.
Treaty teeritory and borders is a border between two civs, but there is nothing there exploitation or settlement wise. This is still not a very "strong" border. It would be possible to have border disputes over these treaty borders. (IE demand a resurveying of the border in diplomacy and If you have become more powerful the other civ may look the otherway when the border changes slightly in your favour. Not accepting a change could be a war excuse that circumvents parliament or the senate in pathetic democracies etc.)
Settled territory forms a more firm border as the populated area has feelings of belonging to the Civ and do not share resources. Borders can not be adjusted through settled territory.
Defended territory is where you have actually stationed defences/guards on a border that is or is not settled. This sort of border can only be changed by military action. Note we could have a border post as a improvement that costs a gold a turn to maintain. You could eventually allow your border posts to just be abandoned but this would be an invitation for someone else to come and make a claim on your territory.
Just a few ideas.