There are two meanings for NM that often get confused on this site, and in the game.
Notorious Monsters are monsters that are extremely rare. They spawn only under certain conditions, have very good standard drops, and rare drops that are usually very valuable. If you "Check" these monsters, their strength will always be "Impossible to Gauge!" regardless of your level. Leaping Lizzy and Jaggedy-Eared Jack are two examples of these types of monsters.
Named Monsters, which people often confuse with Notorious Monsters, are slightly stronger monsters that appear in specific locations, with much greater frequency than Notorious Monsters. These monsters usually do not have very valuable drops compared to Notorious Monsters, but their drops are often required to complete a quest or mission. They are named so the NPCs can tell you what to kill, or so they stand out in the crowd of regular monsters. If you check these monsters, you will get back a normal rating ranging from "Incredibly Tough" to "Too weak to be worthwhile." Warchief Vatgit is an example of a Named Monster.
In general, when someone says "NM" they are refering to a Notorious Monster, but the term is sometimes used for a Named Monster. Many people don't seem to understand the difference between the two, or just don't care.