$\renewcommand{\vec}[1]{\mathbf{#1}}$I came across this problem/idea quite some time ago and was unable to reach a conclusion. (The title of this questions may be misleading. I am open for suggestions.)
Given a (not necessarily orthogonal) basis $\left\lbrace \vec{a}_1,\vec{a}_2,\vec{a}_3\right\rbrace$ of $\mathbb{R}^3$ construct the $27$ points $P = \left\lbrace \vec{k} = k_{1}^a \vec{a}_1 + k_{2}^a \vec{a}_2 + k_{3}^a \vec{a}_3\ \middle|\ k_{j}^a \in \left\lbrace -1,0,1 \right\rbrace\right\rbrace$. For a given $\vec{x} = x_{1}^a \vec{a}_1 + x_{2}^a \vec{a}_2 + x_{3}^a \vec{a}_3 \in D \subseteq \left(\mathbb{R}^3 \setminus P\right)$ find the $\vec{k} \in P$ that minimizes $$\left|\vec{k} - \vec{x}\right|^2 = \sum_i \left(k_{i}^e - x_{i}^e\right)^2$$ where the $^e$ denotes the coordinates of the cartesian unit vectors $\vec{e}_i$, that is, you can write $\vec{x} = x_{1}^e \vec{e}_1 + x_{2}^e \vec{e}_2 + x_{3}^e \vec{e}_3$ and $\vec{k} = k_{1}^e \vec{e}_1 + k_{2}^e \vec{e}_2 + k_{3}^e \vec{e}_3$.
"Problem": Given, that some point $\vec{k}$ minimizes the above expression, can you also conclude that each $\left|k_i^a-x_i^a\right|$ takes its minimum value for all $i$ and vice versa?
I can put some restrictions on $D$, but I want to keep it as generic as possible. Is there maybe some mathematical research that could help me finding a solution?
short answer: it depends
Okay, so this is a fairly complicated question with a fairly complicated answer - I'm just going to walk through everything I did in attempt to solve it, and hopefully provide some useful insight.
First, let's start with a two-dimensional simplification.
Let $\mathbf{e}_1 , \mathbf{e}_2 \in \mathbb{R}^2$, denote the standard Cartesian basis, and...
$$\mathbf{E} = ( \mathbf{e}_1, \mathbf{e}_2 ) = \left( \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right)$$
Let $K=\{ -1, 0, 1 \}$.
In keeping with the original question, let...
$$P_e = \left\{ \mathbf{E} \mathbf{k} \quad \Bigg \vert \quad \mathbf{k} \in K^2 \right\} \quad \text{and} \quad D_e = \mathbb{R}^2\setminus P_e$$
Now, for a given $\mathbf{x}^e \in D_e$, you want to find the $\mathbf{k}^e \in P_e$ such that $|\mathbf{x}^e - \mathbf{k}^e|$ is minimized.
At first, I thought to find a function which returns the closest point $P_e$ to a given point in $D_e$. But then I realized that there are points in $D_e$ which are located the same distance from two or more points in $P_e$ - in particular, points on the lines $x,y=\pm0.5$.
If you label the set of all such points $G_e$, then the points in $D_e$ located closest to a single point in $P_e$ will be in the complement of $G_e$.
For the standard basis, you can find all such points by dividing the plane into nine sectors separated by the lines $x,y=\pm 0.5$ - as shown below. Each sector contains one and only one point in $P_e$, which is closer to each point in the same sector than that point is to any other in $P_e$.
Now for a change of basis. Let $\mathbf{a}_1, \mathbf{a}_2$ denote your new basis. Following what we did with $\mathbf{e}_1$, and $\mathbf{e}_2$, let $\mathbf{A}=(\mathbf{a}_1,\mathbf{a}_2)$
You can make the new sets...
$$P_a = \left\{ \mathbf{A} \mathbf{k} \quad \Bigg \vert \quad \mathbf{k} \in K^2 \right\} \quad \text{and} \quad D_a = \mathbb{R}^2\setminus P_a$$
Like before, for a given $\mathbf{x}^a \in D_a$, you want to find the $\mathbf{k}^a \in P_a$ that minimizes $| \mathbf{x}^a - \mathbf{k}^a |$, and just like before there are points in $D_a$ located the same distance from two or more points in $P_a$. We need to find the set of points $G_a$ satisfying...
$$\forall \mathbf{g}^a \in G_a . \exists \mathbf{u}^a,\mathbf{v}^a \in P_a : | \mathbf{g}^a - \mathbf{u}^a | = | \mathbf{g}^a - \mathbf{v}^a |$$
In the standard basis, these points were just the lines $G_e = \{ (x, y) \mid x = \pm 0.5 \lor y = \pm 0.5\}$. Unfortunately, while the transformation that maps the Cartesian basis to the new basis also maps $P_e$ to $P_a$ and $D_e$ to $D_a$, the same transformation does not map $G_e$ to $G_a$. Instead, the lines in $G_a$ are perpendicular to the boundary of the convex hull of $P_a$ and intersect the midpoints of segments between adjacent points in $P_a$ as shown below.
(green points are $P_a$, red are $P_e$)
While it is certainly possible to work out $G_a$ analytically given this information, it is also extremely tedious (and this is just in two-dimensions). Unless you have a specific purpose in mind, I would advise against it.
Instead of trying to create a formula to compute $G_a$ let's define the function...
$$f (\mathbf{x}^a) = \min \left\{ \left | \mathbf{x}^a - \mathbf{k}^a \right | \bigg\vert \mathbf{k}^a \in P_a \right\}$$
...and have a computer do the rest. A surface plot of this function is shown below.
Notice the ridges? That's where $G_a$ is. You'll also notice that the surface of the plot appears to consist of cones with vertices in $P_a$. This makes sense if you consider that the Euclidean distance from each point is given by...
$$d (\mathbf{x}, \mathbf{k}^a) = \sqrt{ \left( x_1 - k^a_1 \right)^2 + \left( x_2 - k^a_2 \right)^2 }$$
...which is an implicit equation for a cone.
We can interpret each cone as a wave expanding outwards from a source in $P_a$. $G_a$ is the region where the waves meet. As I've found out, this is actually a very well studied phenomenon, and the common model used to describe it, or really any form of radial growth from several point sources, is called a Voronoi tessellation (also, soap bubbles). The regions bounded by $G_a$ are the Voronoi cells whose seeds are $P_a$. A great demonstration of this was created by Tom Walsh using GeoGebra.
For arbitrary $A$ and $\mathbf{x}^a \in D_a$ the Voronoi cells generated from $P_a$ tell you where the nearest point $\mathbf{k}^a \in P_a$ is. If $\mathbf{x}^a$ lies in a particular Voronoi cell, then the nearest point in $P_a$ (the point that minimizes $|\mathbf{x}^a - \mathbf{k}^a|$) will be the seed of that cell.
Now the question becomes: How do the Voronoi cells generated by $P$ transform under change of basis?.
This is a very difficult question and I do not know the answer (for the general case). Fortunately, many efficient algorithms exist for finding Voronoi cells - at the very least you should be able to create a Voronoi diagram for the points $P_a$. Furthermore, even though the example is two dimensional, the premise generalizes to points in $\mathbb{R}^n$. The points in $\mathbf{x} \in \mathbb{R}^n$ which minimizes $| \mathbf{x} - \mathbf{k} |$ for $\mathbf{k} \in P \subset \mathbb{R}^n$ will always be contained within the Voronoi cells generated from $P$.
Hopefully, this helps.
If not, you might try asking an expert in computational and/or convex geometry.