Suppose the entangled particles are generated in a singlet state, $\frac{1}{\sqrt{2}} (\vert 01 \rangle - \vert 10 \rangle)$. If measurement set A is the standard basis, ${ \vert 0 \rangle, \vert 1 \rangle }$, then we would expect the result to be "zero" with probability $\tfrac{1}{2}$ and "one" with probability $\tfrac{1}{2}$.
If I've read your question correctly, it seems that your confusion comes from believing that the measurement results of entangled particles must always be identical. Barring experimental error, this is only the case when the measurement bases, A and B, are identical. If A and B were both the standard basis, then there would be perfect correlation between the A measurements and the B measurements.
If on the other hand, B is a basis like ${ \vert + \rangle, \vert - \rangle }$ where $\vert + \rangle = \frac{1}{\sqrt{2}}(\vert 0 \rangle + \vert 1 \rangle)$, and $\vert - \rangle = \frac{1}{\sqrt{2}}(\vert 0 \rangle - \vert 1 \rangle)$, then we only expect a 50% correlation between the results of A measurements on X and B measurements on Y.
This correlation is still quite good, and is the foundation of Bell-type inequalities, but it is not so good that either party learns anything about the other's choice of basis (or in your terminology: sees a deviation in expected probability based on the decoherence of their counterpart). Both parties always expect to see the "zero" and "one" states with 50% probability - the entanglement only affects the correlation between the remote parties results were they to compare them.
EDIT: @HDE, With respect to the results of measurements in a fixed basis, non-entangled particles are much like weighted coin flips. So the experiment in which the parties have non-entangled particles is not much different from if we let two parties choose arbitrarily weighted coins and had them flip those coins to generate their results. Now, the probability that both parties get the same result is a function of which coin they each chose, if they each chose a coin that's weighted 90% towards heads, then they'll get the same result around 82% of the time. 680
81% of the time they'll both get heads, and 1% of the time they'll both get tails.
Let's look at entanglement, here the probability that both parties get the same result is given by $\cos^2({\theta})$ where $\theta$ is the "angle" between their bases. In my example with singlets above the angle was $\pi/4$ and so there was a 50% correlation between the parties' results. With an angle of $\pi/8$ we see an 85% correlation. This is the key difference, the correlation is governed by the similarity of the bases, not the frequency of particular outcomes. An outcome that occurs 10% of the time will yield a coincidence with probability $\cos^2({\theta})$, which will generally not be 10%. To emphasize this, let's think about the weighted coin flips. If <PERSON> gets a tails on a 90% heads coin, then even in an optimistic case, where <PERSON> chooses the same coin, she only expects <PERSON> to get a tails 10% of the time. With entangled particles, when <PERSON> sees a tails, even if it only occurs one in a million times, she expects <PERSON> to see a tails with certainty assuming he chose the same basis, or with probability .85 if he chose one $\pi/8$ radians off, and so on.
Hope that helps 768