probably the emissaries moved every turn, never stopping, thus making your ninja chase them everywhere. Plus the AI agents use ports, but your own agents won't automatically do the same to follow, so within the span of a few moves, your ninja are hopelessly left behind and may never catch up to the enemy targets. That's why it's a good idea to manually move your agents every turn if possible and try to anticipate which province your target is going to enter, so you can end up on the same territory and be able to attempt assassination.