For convenience let $H(X|Y) = \log(n)$, then
$$ -\infty ~~\leq~~ H(X|Y) - H(X|Y,X\neq Y) ~~\leq~~ \log\left(\frac{n}{n-1}\right) $$
and both sides have tight examples (i.e. as $p\to 0$ it can be arbitrarily negative, and your example matches the upper bound). More specifically, if $p = \Pr[X \neq Y]$, then:
$$ H(X|Y) - H(X|Y,X\neq Y) ~~ \geq ~~ -\frac{(1-p)H(X|Y)}{p} $$
and
$$ H(X|Y) - H(X|Y,X\neq Y) ~~\leq~~ \log\frac{1}{p} + \frac{1-p}{p}\left[\log\frac{1}{1-p} ~-~ H(X|Y)\right] $$
and we have tight examples for the second, and arbitrarily close to tight examples for the first, for every $p,H(X|Y)$.
There will be two steps to the proof: (1) prove an upper bound and matching examples for $H(X|Y,Z)$ where $Z$ is an indicator; (2) convert these to your quantity of interest $H(X|Y,X\neq Y)$.
Upper Bound
Step 1.
Claim 1. Let $Z$ be the indicator for $X\neq Y$ and let $p = \Pr[X\neq Y]$. Then
$$H(X|Y) - H(X|Y,Z) \leq H(p) $$
and for any fixed values of $H(X|Y)$ and $p$, we can construct tight examples.
Proof. The natural quantity to consider is
$$ H(X|Y) - H(X|Y,Z) $$
where $Z$ is the indicator, $Z=1$ if $X \neq Y$ and $Z=0$ otherwise. Let $p = \Pr[X\neq Y] = \Pr[Z=1]$.
Then as Thomas points out, by the chain rule and the fact that $H(X,Y,Z) = H(X,Y)$,
$$ H(X|Y) - H(X|Y,Z) = H(Z|Y) \leq H(p) . ~~~~~~~~ (*) $$
Examples showing tightness: Let $Y$ be distributed arbitrarily; then conditioned on $Y=y$, we let $X=y$ with probability $1-p$ and with probability $p$ we let $X$ be distributed arbitrarily on any set not containing $y$. To be very concrete, you could let $Y=0$ always and let $X=0$ with probability $1-p$ and otherwise $X$ is uniform on $\{1,\dots,m\}$. Choose $m$ to get the desired value of $H(X|Y)$.
In these examples, $H(Z|Y) = H(Z) = H(p)$. So we can make the inequality $(*)$ tight for any $p$ and any $H(X|Y)$. $\square$
Step 2.
"Theorem" 1.
$$ H(X|Y) - H(X|Y, X\neq Y) \leq \log\frac{1}{p} + \frac{1-p}{p}\left[\log\frac{1}{1-p} ~ - ~ H(X|Y) \right] $$
and for any fixed $H(X|Y)$ and $p$ there are tight examples.
Proof. Now, again as Thomas points out, we have
$$ H(X|Y,Z) = p\cdot H(X|Y, X \neq Y) . $$
Now, by plugging in to $(*)$, we have the inequality
$$ H(X|Y) - p\cdot H(X|Y, X\neq Y) \leq H(p) . ~~~~~~~~ (**) $$
and we can make this tight for any $p$. Let $H(X|Y) = p\cdot H(X|Y) + (1-p)H(X|Y)$ and rearrange:
\begin{align}
H(X|Y) - H(X|Y, X\neq Y) &\leq \frac{H(p) - (1-p)H(X|Y)}{p} \\
&= \log\frac{1}{p} + \frac{1-p}{p}\left[\log\frac{1}{1-p} ~ - ~ H(X|Y) \right] .
\end{align}
and, again, we can make this tight using the examples from before (since we have only renamed things and rearranged the inequality). $\square$
Claim 2. For any fixed $H(X|Y) > 0$, as $p \to 0$, we always have
$$ H(X|Y,Z) - H(X|Y,X \neq Y) \to -\infty .$$
Proof. In the bound of the "theorem", for small enough $p$, the upper bound is $\log\frac{1}{p} - \frac{1}{p}\Theta(H(X|Y))$, which approaches $-\infty$ as $p \to 0$ for all fixed $H(X|Y)$. $\square$
Claim 3. For any fixed $H(X|Y)$, we have
$$ H(X|Y,Z) - H(X|Y,X\neq Y) \leq \log\frac{2^{H(X|Y)}}{2^{H(X|Y)}-1} , $$
and there are tight examples. In such examples, $p = 1 - 2^{-H(X|Y)}$.
Proof. Taking the bound in the "theorem" and taking the derivative with respect to $p$, we find that the upper bound is maximized uniquely at $p = 1 - 2^{-H(X|Y)}$. In that case, the quantity inside the brackets is zero, and we obtain
\begin{align}
H(X|Y) - H(X|Y, X\neq Y) &\leq \log\frac{1}{p} \\
&=\log\frac{2^{H(X|Y)}}{2^{H(X|Y)}-1} .
\end{align}
Again, for any $H(X|Y)$, the prior examples with this choice of $p$ make this inequality tight. $\square$
Lower Bound
Step 1.
Claim 4. For any $p$,
$$H(X|Y) - H(X|Y,Z) \geq 0$$
and we can construct examples that are arbitrarily close to $0$.
Proof. As stated above, $H(X|Y) - H(X|Y,Z) = H(Z|Y) \geq 0$. To construct examples arbitrarily close to $0$, fix $p$. The intuition is $H(p)$ is concave, so we will have sometimes $\Pr[Z|Y] = \epsilon$ and sometimes $\Pr[Z|Y] = 1-\epsilon$, so that $H(Z|Y) = H(\epsilon) \to 0$, yet still $H(Z) = H(p)$.
Let $Y = -1$ with probability $1-p$ and $Y = 0$ with probability $p$. If $Y=-1$, then with probability $\epsilon$ we have $X=Y$ and otherwise $X$ is uniform on $\{1,\dots,m\}$. If $Y=0$, then with probability $1-\epsilon$ we have $X=Y$ and otherwise $X$ is uniform on $\{1,\dots,m\}$. Now we can check that $H(Z|Y) = H(\epsilon)$ and $p = \Pr[Z] = (1-p)\cdot \epsilon + p\cdot(1-\epsilon) = p$. Taking $\epsilon \to 0$ gives the example. $\square$
Step 2.
"Theorem" 2. For any $p$ and $H(X|Y)$,
$$H(X|Y) - H(X|Y,X\neq Y) \geq -\frac{(1-p)H(X|Y)}{p} $$
and there are examples arbitrarily close.
Proof. Again we have $p\cdot H(X|Y,X\neq Y) = H(X|Y,Z)$, so by the previous claim,
$$ H(X|Y) - p\cdot H(X|Y,X\neq Y) \geq 0 . $$
Again let $H(X|Y) = p\cdot H(X|Y) + (1-p)H(X|Y)$ and rearrange. By the previous claim, we have arbitrarily close examples (since we have only rearranged the inequality). $\square$
