Since Pietro Majer definitely was right about the structure of the set but hasn't supplied a proof let me jump in with an elementary one. I think the problem is to specific to find a reference, but it might have occurred to others in some context unbeknownst to me.
Lemma: If the closest point in $X$ is always directly above and below then all connected components of $\mathbb{R}^n \setminus X$ are of the form $\mathbb{R}^{n-1} \times (a,b)$.
Pick a point $(\bar x_0,x_n) \in \mathbb{R}^n \setminus X$. We can assume wlog. that the closest point in $X$ is above (and that it is close than the one below by some margin). Define $$f^+_{x_n}: \mathbb{R}^{n-1} \to \mathbb{R}, \bar{x} \mapsto \inf \{s \geq 0: (\bar{x},x_n+s) \in X\}.$$
Set $r := f^+_{x_n}(\bar{x}_0) = \operatorname{dist}( (\bar x_0 , x_n),X) >0$. Now there is no point in $X$ closer to $(\bar x_0,x_n)$ than distance $r$, we know that $B_r(\bar x_0,x_n) \cap X = \emptyset$. But translated to $f^+_{x_n}$ this means that for any $\bar x$ with $|\bar x - \bar x_0| < r$ we have to have
$$f^+_{x_n}(\bar x) \geq \sqrt{r^2 - |\bar x - \bar x_0|^2 }.$$
Next consider any point close to $(\bar x_0,x_n)$ with distance $r$ to $(\bar x_0,x_n +r)$, i.e. of the form $(\bar x, x_n + r-\sqrt{r^2 - |\bar x - \bar x_0|^2 })=: (\bar x,y_n)$. Then we have $\operatorname{dist}( (\bar x, z_n),X) \leq r$ and the closest point again needs to be above (otherwise the closest for $(\bar x,x_n)$ would be below). But then this tells us that
$$f^+_{x_n}(\bar{x}) \leq 2r-\sqrt{r^2 - |\bar x - \bar x_0|^2}.$$
But now the function $f^+_{x_n}$ is wedged between two $C^\infty$ functions which meet each other with derivative 0 at $\bar x_0$, so we have to have $\nabla f^+_{x_n}(\bar{x}_0) = 0$ as well. But the same works for any point at which $f^+_{x_n}$ is nonzero, which includes all $\bar{x}$ with $|\bar x - \bar x_0| < r$. So $f^+_{x_n}(\bar{x}) = f^+_{x_n}(\bar x_0) = r$ for all those $\bar x$. The same argument for some $y_n < x_n$, for which $(\bar x_0,y_n -r)$ is the closest point to $(\bar x_0,y_n)$ in $X$, gives us that a similarly defined $f^-_{x_n}$ is constant on the same ball around $\bar x_0$ and then iterating the argument allows us to arbitrarly extend the domain on which this is true, which proves the lemma.
Corollary: This also works if the condition is only true for $ r < r_0$ fixed, one just has to pick points close enough.
This then lets us give an answer to the question: The set $X$ will always be of the form $\mathbb{R}^{n-1} \times F$ for some closed set $F$. Thus if you additionally enforce $d$-dimensionality of $X$, you'll get that $F$ is $d-(n-1)$-dimensional, so in particular $X = \emptyset$ for $d < n-1$ and a countable union of isolated planes for $d=n-1$.