Maybeso, but ... if Saadia was cozy with the Thalmor, why don't the Thalmor protect her? Simply because she's no longer useful? That part kinda nags at me.
Also, I agree with Chrysoscolla, the way they harass random redguard women had me inches away from gifting them with honorable deaths in combat. Also, when I ask why they want her they refuse to answer saying if money is not enough motive, go away.
Two reasons:
1. The guys walking the roads weren't in charge, likely weren't authorized to give reasons, and certainly aren't going to trust those reasons to random strangers (they also don't seem to be terribly bright).
2. If they let spread around exactly who they were looking for and why, Saadia would have ran again, right out of Skyrim and into some place that would have been even harder for them to search.