Casascius' Bitcoin Address Utility includes a Base58 calculator. You can input into it the lowest and highest values to encode to obtain the lowest and highest strings.
For example, to get the lowest Namecoin address, start with the hex representation of its network byte 52, which is 34, and add 40 zeroes (representing the 160 bits of the public key hash in hex). The result is MvaNCeVyvP6ZXYFWGpKaDX9ujEQ418F7sm. Likewise, to get the highest string use 34 followed by 40 f's, giving NKuyBkoGdZZSLyPbJEetheRhMjezbtjJCf.
Only 34-character strings which are between these two, in lexicographic ordering, can be valid Namecoin addresses. The ordering of the characters is compatible with ASCII, 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz, and thus most programming environments should be able to check the address with the built-in string comparison functions.
Specifically, the first 2 characters can only be one of the combinations between Mv and NK, which are Mv, Mw, Mx, My, Mz, N1, N2, N3, N4, N5, N6, N7, N8, N9, NA, NB, NC, ND, NE, NF, NG, NH, NJ and NK.
A more general approach is to decode the address into a number, and verify that the result is composed of the required version byte followed by any n bits (where n is the bit length of the encoded data, 160 in the case of a receiving address).