We prove that for $\mathbb{Z}^d$ ($d\ge 2$), the vertex-removal stability of harmonic measures (i.e. it is feasible to remove some vertex while changing the harmonic measure by a bounded factor) holds if and only if $d=2$. The proof mainly relies on geometric arguments, with a surprising use of the discrete Klein bottle. Moreover, a direct application of this stability verifies a conjecture of Calvert, Ganguly and Hammond [9] for the exponential decay of the least positive value of harmonic measures on $\mathbb{Z}^2$. Furthermore, the analogue of this conjecture for $\mathbb{Z}^d$ with $d\ge 3$ is also proved in this paper, despite vertex-removal stability no longer holding.