Are there any combination of letters that a namecoin address cannot start with? It recently came to my attention that some Namecoin addresses might not be generated at all (see https://bitcointalk.org/index.php?topic=84569.msg1370025#msg1370025 ). Namely, there are issues with generating addresses starting with 

Na, Nb, Nc, Nd, Ne, Nf, Ng, Nh, Ni, Nj, Nk, Nm, Nn, No, Np, Nq, Nr, Ns, Nt, Nu, Nv, Nw, Nx, Ny, Nz, NL, NM, NN, NP, NQ, NR, NS, NT, NU, NV, NW, NX, NY, NZ

Is there some reason behind it, or is it just some vanitygen bug?
Namecoin addresses, like Bitcoin addresses, are Base58 encodings of a public key hash. The encoded data starts with a version byte, and the value of this byte affects the first characters of the result.

Namecoin addresses specifically use a version byte of 52, which dictates a certain range of initials. The prefixes you listed are simply too high - they correspond to a version byte of 53 or even 54. Likewise, some prefixes starting with M are impossible because they correspond to a version byte of 49, 50 or 51. You could give a more precise "lowest" and "highest" addresses, in lexicographic ordering - the address must be between MvaNCeVyvP6ZXYFWGpKaDX9ujEQ418F7sm and NKuyBkoGdZZSLyPbJEetheRhMjezbtjJCf.

A full list of version bytes and first characters is available here, and the possible 2nd character ranges can be interpolated from it. For version bytes 0-2 and 144-255 the address length can be different from 34 so it makes the ranges less intuitive. But for 3-143 it's fairly straightforward: You have about 58^2 possibilities for first 2 characters to go between 141 version bytes, so each is only allocated a range of about 23 combinations. For Namecoin addresses that would be Mv to NK.