I will give two cases, where the rule replacement works in the first one and does not work in the second one, but they are essentially the same!
Consider the following definition, whose details are not important:
vall = -Sqrt[Δ^2 + μ^2 + 2*μ*Sqrt[px^2 + py^2] + px^2 + py^2]
Now, we check the following:
vall /. {ϕ -> 0, py -> pyy, px -> 0, μ -> 0}
As expected, I can obtain the desired replacement:
Now, consider the following expression, which contains the above expression as a subexpression:
Exists[
{py, pyy},
123 == (vall /. {ϕ -> 0, py -> pyy, px -> 0, μ -> 0}) == 0 ]
The result is surprising:
As can be seen in the picture, no replacement py -> pyy
is made!
Why does this happen?