How is the One Time Pad (OTP) perfectly secure? The Wikipedia entry on One Time Pads (OTPs) states that if this cipher is used properly; ie, the keys are truly random and each part of the key is independent of every other part, it's uncrackable, and yields perfect secrecy, i.e., $H(M|C) = H(M)$.

It gives an example saying that a cryptanalysis on a plaintext "HELLO" will yield all plaintexts like "HELLO", "LATER", with equal probabilities.

Now, consider some OTP encrypted data that I know are English sentences. With infinite computational power, I generate all plaintexts. Now, becasuse each word of the sentence is related to nearby words, I can at the very least narrow down the list of possibilities (I don't know the combinatorics of cramming English sentences into M letters), which does not equal perfect secrecy (entropy $H(M)$ appears to have decreased!).

In short, OTP guarantees $H(M|C) = H(M)$, but my question is that $H(M)$ will be reduced by knowledge of the plaintext, so how is prefect secrecy being ensured?
You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext.

This is not true as you have observed.

The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this:


  Definition 2.3 An encryption scheme $(\text{Gen, Enc, Dec})$ with message space $\mathcal M$ is perfectly secret if for every
  probability distribution over $\mathcal M$, every message
  $m\in\mathcal M$, and every ciphertext $c\in \mathcal C$ for which
  $\Pr[C=c]&gt;0$:
  
  $$\Pr[M=m\mid C=c]=\Pr[M=m]$$


In other words, if you have the ciphertext at hand, you won't learn anything new that you didn't already know about the plaintext.

The OTP satisfies this (proved in "Introduction to Modern Cryptography") and thereby is perfectly secret as an encryption scheme. In short it first shows that $\Pr[C=c\mid M=m']=2^{-l}$, then uses this to show that $\Pr[C=c]=2^{-l}$ and concludes via $\Pr[M=m\mid C=c]=Pr[M=m]$ (using Bayes' theorem).