If the ruler was already banned in the other realm, then yes, he could be executed if caught. But you would have to catch him first. There are a limited number of ways to capture a noble. The one that probably got the guy in your case was traveling in an enemy region (diplomatic status of War) without a unit. If he was traveling without a unit into a realm with which he was at war, then he deserved to be executed.
