Let $G$ be a group and $N$ a subgroup. Consider the condition $$(\forall g\in G)(\exists x,y\in G)\ NgN=xNy.\tag1$$
If $N\lhd G$, then for each $g\in G$ we have $NgN=gNN=gN=gN\cdot1$, so the condition is satisfied.
Suppose $G$ is finite and condition $(1)$ is satisfied. Then by this, we have, for any $g\in G$, $$|N|=|xNy|=|NgN|=\frac{|N|^2}{|N\cap gNg^{-1}|},$$ and therefore $$|N\cap gNg^{-1}|=|N|.$$ Since $N\cap gNg^{-1}\subseteq N$ and $N$ is finite, we have that $N=gNg^{-1}$ for all $g\in G.$ This means that $N$ is normal in $G$.
Is this true in general that condition $(1)$ is equivalent to $N$ being normal in $G?$ There are three similar conditions: $$(\forall g\in G)(\exists x\in G)\ NgN=xN.\tag2$$ $$(\forall g\in G)(\exists y\in G)\ NgN=Ny.\tag3$$ $$(\forall g\in G)(((\exists x\in G)\ NgN=xN)\vee(\exists y\in G)\ NgN=Ny)).\tag4$$
Perhaps one of them works? (The first one is the one I first encountered, more or less naturally, which is why I used it. But it is clear that the other conditions work just as well for what I did. I don't know what happens for infinite groups.) $(1)$ is the weakest of the conditions, so if it implies that $N$ is normal, the others do too and, in consequence, all are equivalent. So to show that $(1)$ doesn't imply that $N$ is normal, it's enough to show that $(1)$ doesn't imply one of the other conditions. Please correct me if this is wrong.
I believe there is an example of a non-normal subgroup satisfying (1) (and also (4)).
Let $G = \langle x,y \mid y^{-1}xy = x^2 \rangle$ and $N = \langle x \rangle$. Then $y^{-1}Ny < N$ but $yNy^{-1} \not< N$. (This group can also be defined as a group of $2 \times 2$ rational matrices.)
So, for all $k > 0$, $Ny^k < y^kN$ and $y^{-k}N < Ny^{-k}$ and hence $Ny^kN = y^kN$ and $Ny^{-k}N = Ny^{-k}$, which proves (1) and (4) when $g$ is a power of $y$.
The normal closure $K$ of $x$ in $G$ is an infinitely generated abelian group generated by elements $x_n = y^{-n}xy^n$ for $n \in \mathbb{Z}$, where $x_0=x$ and $x_n^2=x_{n+1}$. An arbitrary element $g \in G$ can be written as $y^kx_n^j$ for some $k,n,j$, or alternatively as $x_n^j y^k$ (with the same $k$ and $j$ but a different $n$). Since $K$ is abelian, each $x_n$ commutes with $N$, and so we get Condition (4) for all $g \in G$.