I do not think that entering another player's border's should be an act of war (unless you are hated and have been banned from entering their lands, in which case you are practically at war anyway).

Wehn you first find another players borders, like Scoutdog suggested in another thread, you shouldn't see the owners colored border, you just see land that has been healed by a channeler.

When you contact another players units, the borders should become visible to you in areas that you have explored. Similar to spheres of influence in GalCiv. On a side note I hope that map sharing is one of the diplo trade options.(you swap what you have explored at the time of the trade and your maps are updated accordingly).

Once you have contacted a civ you can parlay for rights of passage or whatever else.

When you cross a border with someone that you do not have a right of passage agreement with, it still should not be an act of war. Instead if you are not spotted in the borders, nothing happens. When you are spotted, the diplomacy screen opens and depending on your relationship at that point one of several options might happen:

1. If you have very unfavorable relations the AI might declare war on you with no options (also based on the AI personality)

2. The AI may offer to escort you to the border and avoid war "for a fee".

3. The AI might be willing to arrange right of passage agreements - but expect to pay extra to get it since you encroached without having the right of passage

4. Any option more mild than this and you likely already have a right of passage agreement - if you are already on friendly terms the AI might just offer to exchange right of passage agreements (reciprocal) with you.

I also suppose there could be an option that your borders are posted with "no trespassing" signs which basically says "If you enter without permission - u r ded.