[Alneyan]

Good catch about Machaka and spies. Marignon and Machaka also have assassins, in addition to Pythium, and Abysia does too; in addition, there is a site allowing anyone to recruit them if memory serves.

You can get a random event where the independents try to assassinate one of your commanders too, and that seems to be the more likely explanation here.