In the days, changing realms automatically resulted in a ban from one's old realm.
I feel that should still be the case when a noble abandons a realm for a realm that they're at War or Hatred with. It would make spying like what the OP described a real risky proposition for the spy (if he gets caught by this old realm "why did they execute you?", when he goes back the realm he spied on has the chance to execute him if they catch him).
