The Empire has martial law in the Empire, The Thalmor only have the ability of stamping out Talos worship which they could barely do because the Empire doesn't allow them to go around kicking down doors and dragging people off in the night, the Thalmor can only enforce their terms to a very limited point while the Empire is watching them. Twenty six years in Skyrim there was barely any incident with the Thalmor, they need evidence before being allowed to touch a citizen of the Empire, like the quest in Markarth you need to find evidence of talos worship because the Empire supporting Jarl won't let the Thalmor arrest or detain him.
The Thalmor don't have supreme powers, they only gained the ability to do what they wanted during the Civil War since there isn't a large number of Empire soldiers keeping their eyes on them, gives the Thalmor free access to go around unchecked and unchallenged.
Ulfric allowed the Thalmor to put pressure on the Empire on treaty enforcement. Before Ulfric the treaty was poorly enforced.
We didn't pay much attention to it when I was a boy - everyone still had their little shrine to Talos. But then Ulfric and his "Sons of Skyrim" started agitating about it, and sure enough the Emperor had to crack down.
So the Thalmor do not have this unlimited power many Stormcloak supporters try to make out. Markarth is quite evident as to what the Thalmor can do under the watchful eye of the Empire. They need proof to make an arrest, not hearsay.