I like the idea of land claims (or territory bargaining in general), but I don't like the implementation as thought in the opening post, nor do I really like Boris' implementation (100+ Civs would be way too complex
I already have trouble keeping track of the international state of affairs when there are 31 simultaneous Civs). Besides, I think Boris' implementation is not flexible enough, because of its strongly limited timeframe.
There are 3 ideas I'd suggest for "land claims":
1. You can claim unclaimed tile simply by bringing a fighting unit there, and letting it fortify for at least one turn. If the unit moves, the territory stops being claimed.
In order to claim a large unsettled territory (such as Siberia), I think these borders should behave a bit like in Civ3: when one tile separates two tiles belonging to the same Civ, that "unclaimed" tile automatically belongs to that Civ. As a result, to claim whole areas, you'd have to put a unit once every two tiles.
2. Foreign cities cannot be founded in your borders, but their own borders will always be stronger than your claims: if a foreign city can culture-get a tile you have claimed, it will always get it.
3. I think "land claims" should be possible only after a tech has been discovered, probably a tech associated with the age of exploration (that's where I chime in with Oncle Boris). Printing Press, Navigation, Banking, or some exploration age Government tech could do the trick in making land claims possible.
As per land bargainings, I think a simple interface should allow it once an adequate, middle ages tech had been discovered (Monarchy?)
There is one limitation I'd like to see, however, it is that the bargained tile would come back to its legitimate (culture wise) owner if it remains unoccupied by a unit for X turns. That would make it possible for the military player to increase its borders without too much culture, but that would force such a player to pay a real price for it.
Also, if you bargain "claimed territory" (one that doesn't have any culture-legitimate owner), the results of the bargaining win over the claim: the "claiming" unit will have to pack if the tile is given to somebody else. However, the territory would revert back to "unclaimed" status if no troops occupies it for X turns.
I'm really fond of enabling these features only after some time in the game. The first reason is that I generally like not to have all the possible options up front (this way, things are much more simple and progressive for the newbie, and more exciting for the fan who strives to unlock abilities).
But the second reason is that culture should play an important role in the early game, when unsettled territory is the norm and settled territory is the exception. In early game, it's much easier to build a warrior / militia than a settler or a temple, and claiming territory like that would mean every ancient Civ would neglect culture and settler building, to grab land as quickly as possible with warriors