The Right of Passage treaty should be a bidimensionnal treaty (like alliance, if you have a RoP with a race, that race has a RoP with you) that allows military ships to travel into another race space without triggerring build up warning from the AI. That way, you could help an ally in another part of the galaxy without annoying a neutral race by having your fleet passing near its planets. In short, a race which whom you have a RoP treaty shouldn't declare war against you for military build up concern.
The cancelling of a RoP treaty should be treated for ships like a declaration of war with the UP issue that enforce relocation of ship. The cancellation could be made in the diplomatic screen by specifically cancelling it. And naturally, you can't have/maintain a RoP treaty with a race if you are at war with that race
My two cents worth (if it is even worth that much!)...

I like what Peace Phoenix said above. It seems simple enough and does not seem to be much in addition to what is already in the game. If there is no RoP then foreign military ships would trigger a build-up warning as Peace Phoenix said. To expand on this, the build-up warning would not necessarily mean that the other race would declare war but would add a negative point in your relations with that race (perhaps a double negative if you have LOTS of military ships in their space). The AI could warn you to remove your military ships from their space if you don't have a RoP with them if your ships have triggered a build-up warning for them. This warning would be similar to the warning that they give you when you have a couple of strong influence starbases next to their planets.
I think that it is OK to move ships out of another races culturally controlled space if a RoP is cancelled (either diplomatically or through the declaration of war). I have never found the UP event like this silly - it just adds another thing to consider when I play which is good for variety (and I haven't seen anyone complain about the UP event before the RoP topic started so why start complaining now!

). If you don't have a RoP with another race then you can still launch a sneak attack but your ships would have triggered a build-up warning with the AI race and so they should be watching you closely (not to mention the cool relations that you would have with that race due to the negative point that your ships in their space without a RoP are causing to your relations with them).
If people are worried that moving ships out of culturally controlled space will then leave planets that are within in another races influence unprotected then perhaps ships should also be moved to within the squares immediately around a planet owned by the owner of the ships even if all of that space is technically in the influence of another race. Alternatively, Cari's idea about returning the ships to the world where they were build is another OK suggestion (except that planets have a limit (10 ships?) to how many ships can be in orbit so I don't know how her suggestion would work with this limitation.
As a semi-side note, I think that implementing actual borders (instead of just using cultural borders as a quasi-border) is silly!

This is space. Sure your race might have influence over a large portion of space but it is not really owned by anyone. What are you going to do to declare ownership? Put up a big fence? Remember that space is 3D so the fence would have to be a sphere. Also, if there are actual borders then what happens when there are two planets in the same star system owned by two different races? It would be complex and annoying trying to determine a good way to fairly and logically handle actual borders in instances like this. I think that actual borders *would* add too much complexity without any (or much) benefit to gameplay.