I suggest closed borders and treaties that allows one to cross some ones border for x turns, where x is the players/A.I.'s own choise. A.I.'s would only accept this if relations are high. Of course attacking while using this treaty should come to a major diplomatic penalty (-3 for this kind of attack alone).

This is how it was in WOM.

I didn't like that mechanic, I don't like it in Civ either.  I think sneaking across borders should be part of the game but there needs to be a stiff penalty for getting caught so that players aren't constantly having to enforce it.

Would it make sense to have a 2-3 turn grace period for both players and AI before the AI starts getting gritchy? I can see a "Just Passing Through" grace period for any faction that isn't at war with you after which you get asked to leave.

That's generally about the point that I bring the hammer down...

The issue isn't so much sneaking, though that is a good concept. The issue for me is making the players choose between bad relations for kicking out a friend or losing that 5/3 spot you just know he is going to steal. Enemies and rivals should get kicked as soon as they cross and maybe being on Hostile terms means you have to declare war to even enter their territory.

      You know, this is a good reason to have stealth units in the game, and stealth type spells, and terrain walking to circumvent zones of control. I'm not sure about your idea of taking away the closed borders froggy - unless you make it easier to start and end wars - or include more treaty types, some temporary some not. Maybe a toggle switch for open/closed borders.

     The most important thing about the closed borders is that it forced interaction with the computer factions - they have their goals and you have yours, so there is room to negotiate. Given that the factions will be better defined in the next beta, they will have their own individual goals - some ai should lean towards the adventuring win, some towards the spell of mastery, and some towards military victory. The point is each faction will value resources differently and will be willing ot trade.

       Settlers of catan is a good example. you have several ways of winning the game, the basic goal being to gain 10 points. However you gain points for investing in the most roads, and points for investing in the largest standing army, and points for upgrading your towns into cities. Each of these contribute to winning the game but they require vastly different resources to pull off. I may want to be king of the roads, but i will have to make a city to get missing points so i need to talk to the person in control of the grain and stone and see if he wants my brick and wood. We both want things which we need to win, it is just a question of how much we are willing to trade with each other.

     I like the idea of 3 or 4 turns grace before being kicked out by the comp, repeat offenders have war declared on them.

     temp caravan treaty with other factions builds a road from capital to capital, no vision from caravans, when treaty expires the road dissapears. If you decalre war the road dissapears. If you get too close to enemy faction towns with aggresive units the treaty expires and the road dissapears.

     resource treaty with other faction you give some resources to a faction and they pay with other resources for a number of turns.

     stealthiness might give the dex/ assassin champions and sovereign that extra kick they need.

Of course, then you need detection spells too.

(any chance of an insert tab button being added to the menu? hitting space bar so many times can lead to tendinitis )

I would love this ability, it's not gamey at all like would be an entire army dissapearing without reason/spell, and one could still make it so that there is a negative occurance with relations too.  If you can see'em you can killem (maybe), or open negotiations or just let it pass. 

Yes.  Stiff penalties.

I also think there should be diplomatic options for opening and closing borders which are independent of being allied or not.  Of course these may also have an effect on the friendliness of the other realm.