To be honest, having thought about it a bit, I'd like to see the addition of closed borders as an extra diplomatic option - so you have 'normal', 'open borders' AND 'closed borders'.
Normal would be pretty much how it is presently; they can enter your space but there's a relations penalty. This should stack for every unauthorized intrusion. The AI should be coded to be aware of this, and so should auto-exploring ships. The stacking effect should make an AI grow hostile very rapidly if you move 60 transports in to hover over his planets, but should make it less angry if 1 or 2 scouts happen to blunder in (I'm kind of sick of seeing the AI getting pissed at me the moment we meet because my scout had to fly into his influence). This is the absence of either open or closed borders.
Open borders would remove all penalties from moving in enemy space, though the AI should still remain aware of influence and avoid settling in someone else's simply because it's a very stupid thing to do most of the time. I have never once seen any AI planet that is settled within an area of reasonably established influence avoid being flipped to me eventually.
Closed borders would allow you to basically warn an enemy that any future entry into their space will be treated as an act of war. Any ships you have in their space should be forced to move directly out of their influence, like ships that are out of range do. Any attempt to move into their space is immediately greeted with an 'are you sure, this will declare war on this guy?' message. All trade routes are cancelled. If planets or SBs are on the wrong side of the border... tough luck, you shouldn't be dropping stuff on a potentially hostile power's turf.
