This is a question that is relatively easy to answer mathematically.
To keep the algebra a little simpler, let me use a simplified Michaelis-Menten mechanism, where we assume that the enzyme-substrate complex (ES) and the free enzyme are in equilibrium. (We could use the less restrictive pseudo-steady state hypothesis on (ES) and obtain the same result for non-competitive inhibition, at the expense of more complicated math.)
$$\ce{E + S <=>[K_M] (ES) ->[k3] E + P}$$
Non-competitive inhibition means that the inhibitor doesn't care at all whether the substrate is bound to the enzyme. Either on (ES) or on (E), it will bind with affinity $\mathrm K_{\mathrm i}$. We assume that (ESI) does not react, at all, to form products. So the only other two reactions we need are:
\begin{align}
\ce{E + I &<=>[K_i] (EI)}\\
\ce{(ES) + I &<=>[K_i] (ESI)}
\end{align}
Now to get the rate equation, we first perform a mass balance on enzyme:
$E_0 = E + ES + EI + ESI$
We use the equilibria we've assumed above to get:
\begin{align}
(ES) &= \frac{(E)(S)}{K_M}\\
(EI) &= \frac{(E)(I)}{K_i}\\
(ESI) &= \frac{(E)(S)(I)}{K_M K_i}
\end{align}
Thus
\begin{align}
E_0 &= E\Big(1 + \frac{(S)}{K_m} + \frac{(I)}{K_i} + \frac{(S)(I)}{K_M K_i} \Big)\Big)\\
E &= \frac{E_0}{\Big(1 + \frac{(S)}{K_m} + \frac{(I)}{K_i} + \frac{(S)(I)}{K_M K_i} \Big)}
\end{align}
The rate equation we are after is just the formation of product, $\frac{dP}{dt}=k_3 (ES)$.
$$k_3 (ES) = k_3 \frac{(E)(S)}{K_M}$$
Now we know $(E)$ from our enzyme mass balance, so
\begin{align}
\frac{\mathrm{d}P}{\mathrm{d}t} &= k_3 E_0 \frac{(S)}{K_M \Big(1 + \frac{(S)}{K_m} + \frac{(I)}{K_i} + \frac{(S)(I)}{K_M K_i} \Big)}\\
&=k_3 E_0 \frac{S}{K_M + S + \frac{I}{K_i}\left(K_M + (S)\right)}\\
&=k_3 E_0 \frac{S}{(K_M + S)\cdot (1 +\frac{(I)}{K_i})}\\
&=\frac{k_3 E_0}{(1 +\frac{I}{K_i})} \frac{S}{(K_M + S)}
\end{align}
The only thing different about this expression is that the "$V_{max}$" part of the expression, which would have been $k_3 E_0$ for a simple reaction with no inhibitor, is now $\frac{k_3 E_0}{1 + I/K_i}$. In other words, $V_{max}$ is the only parameter changed by the inhibition mechanism we have assumed.
The apparent $K_M$ of the non-competitively inhibited reaction is still $K_M$, because if you plug in $S = K_M$, you get a rate that is half of the maximum (of the inhibited reaction).
Wikipedia attributes the invariance of $K_M$ in non-competitive inhibition to the fact that the actual binding of substrate to an active site is unaffected. Now I agree that the actual binding of the substrate is unaffected here...but how does that have any effect on $K_M$?
You can think of $K_M$ as an apparent equilibrium constant for the binding of substrate to free enzyme. So if something doesn't affect substrate binding, it probably won't affect $K_M$.
So, when $V_{max}$ decreases during non-competitive inhibition (the only point I and Wikipedia concur on), shouldn't the $K_M$ decrease correspondingly (based on the definition of $K_M$? Is the Wikipedia article incorrect in this regard?
No, Wikipedia is correct. Enzymologists have adopted very confusing terminology for no good reason, but non-competitive inhibition is not the same uncompetitive inhibition. In uncompetitive inhibition, both apparent $K_M$ and apparent $V_{max}$ are changed.
If I gave you two vials, A and B, of the same enzyme, and one of them had been pre-mixed with a high concentration of a non-competitive inhibitor, and I asked you "what's the $K_M$ you measure for each of these two different enzyme preparations?," then you'd get the same number for each vial. If 5 mM of substrate is the concentration at which enzyme from vial A reaches half of its maximum rate, then you'll find that 5 mM of substrate is also the concentration where enzyme from vial B reaches half of its maximum rate.