Why does the Michaelis-Menten constant remain constant in the event of non-competitive enzyme inhibition?
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 &lt;=&gt;[K_M] (ES) -&gt;[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 &amp;&lt;=&gt;[K_i] (EI)}\\
\ce{(ES) + I &amp;&lt;=&gt;[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) &amp;= \frac{(E)(S)}{K_M}\\
(EI) &amp;= \frac{(E)(I)}{K_i}\\
(ESI) &amp;= \frac{(E)(S)(I)}{K_M K_i}
\end{align}

Thus 

\begin{align}
E_0 &amp;= E\Big(1 + \frac{(S)}{K_m} + \frac{(I)}{K_i} + \frac{(S)(I)}{K_M K_i} \Big)\Big)\\
E &amp;= \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} &amp;= 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)}\\
&amp;=k_3 E_0 \frac{S}{K_M + S + \frac{I}{K_i}\left(K_M + (S)\right)}\\
&amp;=k_3 E_0 \frac{S}{(K_M + S)\cdot (1 +\frac{(I)}{K_i})}\\
&amp;=\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.