The truth is we need to come up with a "controlled" border and a "cultural" border.
I don't agree with this on the grounds that borders in space really don't make sense and trying to enforce a border system would be a micromanagement mess.
Sorry this is long guys. I had to throw in my two cents here. And I feel this can be done in a reasonable way, that isn't gamey, and isn't extreme on the coding side either. I had to put this out here, despite its length.
I'm not sure why something like borders should be hard to code, separately from influence. Borders just need to be a specified radius around a planet. Your borders are what you own, physically, ie. land. In other words, if you own the planet, then you have a claim to a certain radius around the planet. This can be two parsecs, or eight, for all I care. And it could even be a startup option, to add more choices to the game. And to be clear here, star bases have no effect, they are ships without engines, not territorial claims (that requires ownership of land). Your borders are nothing more then a radius around your planets, which should be very easy to code.
And the UP can even vote to let the races decide exactly what size should be the internationally (galactic) accepted zone size. Just as our UN and current international law recognizes three miles of ownership out into the ocean.
Now, that just does not seem remotely difficult to me to be able to code. But then it leaves the next question, of how to handle it when someone enters your territory without a right of passage treaty. And that doesn't have to be too terribly complicated either.
Simply, if they are in your territory, we can have multiple options for solving the issues. If I attack someone within my territorial borders, I get a pop up with two choices, 1) attack (declare war), or 2) diplomatic ejection (i.e. that ship gets teleported back to their home or nearest planet). This isn't exactly unrealistic. Nations eject diplomats, or deport people, or whatever the case may be all the time. Calculate the time it would have taken to make the journey and wait that amount of time before making it available again. It's part of the price you pay for getting caught, and it keeps it more realistic (we are simulating that it was deported and had to travel back).
Now, we can try to run the blockade, so to speak. And the other side has to actually catch us to stop us. Yet we can be caught and ejected, or it could possibly even start a war. We have options, not restrictions. And that's for both sides involved in the issue. Perhaps a planet we own requires us to "run the gauntlet" because its deep behind the lines within another's territory. And different AI personalities can have different tendencies for their response (of course balanced if they simply can not win a war).
And then you could expand the right of passage with more flavors. Full right of passage, or just trading rights of passage. Or if we "really" wanted, only rights of passage through the borders of a specific set of planets. Or, even better, another right of passage for specific types of star base construction. Again, more options makes for a better game and I'll bet others can be creative and come up with more variations, that really wouldn't be too much more to code.
Continuing on, we now can have disputed zones where two planets have overlapping radius zones. In disputed zones, you can't diplomatically eject the other side any longer. You either attack and declare war, to decide who really owns it, or you acknowledge their right to be there. Simply, if it's a disputed zone, you can't diplomatically eject them any longer. I can park on their doorstep and they can't eject me (because I do have as much claim to be there as they do). But it might be that they don't like that and are willing to fight as a remedy.
The gamey things are lame. And I wholeheartedly agree that simply teleporting them 100 parsecs or artificially slowing them down degrades the game, rather than enhances it. And I don't feel those are "minor degradations" either.
We are adding layers of play to the game this way. Cloaking comes to mind, when thinking of even more ways to add options and playability here.
One last point here. With borders being a simple radius around your planets, we have added an additional layer of game play by making that radius adjustable in the options or by UP vote. Some of us like to put influence star bases near other races planets. All of a sudden, depending on how large that radius is, those star bases may not be buildable up close and personal. Make it so you can't build a star base in someone else's territory, without a forced declaration of war, or star base right of passage. This brings in more playability, such as what happens if you have a star base somewhere (with right of passage), but the territory it's in changes ownership? The other side can ignore our star base, or attack (giving the option of 1. attack, or 2. force owner to sell it off, or 3. capture it with troops). And why not make all star bases capturable, for that matter.
This is adding simple, yet significant playability options, and it keeps it reasonably realistic. And it seriously should not be hard to code a radius or number of parsecs outward from a planet, to determine territory. Please consider some of this.