The case of Huan is similar, and instructive, because someone did try to cheat. Huan was a wolfhound, and there was a prophecy saying that he could only be killed by "the greatest wolf that ever lived". Sauron (yes, that Sauron) turned himself into the greatest wolf that had ever lived, attacked Huan — and was defeated. Some years later, Huan was slain by a still mightier wolf, Carcharoth, who had not yet been born when Huan fought Sauron. (I don't recall whether Sauron was unable to fulfill the conditions because Carcharoth had not yet been born, or whether he simply became the greatest wolf he could and that wasn't enough.)

So with the Witch-King: it's not that no "man" ever tried to kill him, or even that no man came close; it's that none of them succeeded. If one of them had succeeded, Glorfindel would have seen something different.

(We might conclude from this that the history of Arda is knowable in advance, and I think that's consistent with the way Ainulindalë presents the creation of the world.)

The case of Huan is similar, and instructive, because someone did try to cheat. Huan was a wolfhound, and there was a prophecy saying that he could only be killed by "the greatest wolf that would ever live". Sauron (yes, that Sauron) turned himself into the greatest wolf that had ever lived, attacked Huan — and was defeated. Some years later, Huan was slain by a still mightier wolf, Carcharoth, who had not yet been born when Huan fought Sauron.

I don't recall exactly how it's put, and don't have a copy of The Silmarillion to check, but I believe it is made reasonably clear that Sauron could not qualify as "the greatest wolf that would ever live" because that was Carcharoth. That position was already taken.

So with the Witch-King: he must have fought plenty of "men" (however we define that) in the course of his career as a warlord, conqueror, and Ringwraith, but it was Eowyn and Meriadoc who killed him, and Glorfindel predicted that "not by the hand of man will he fall" because it was Eowyn and Meriadoc who killed him. In the scientific terms familiar to us here in the Fifth Age, the causality runs backward in time; if he had fallen in some other way, Glorfindel would have seen something different.

(One can interpret Ainulindalë to be saying that the entire history of Arda is laid out in the Music of the Ainur, and therefore any event is knowable in advance, although only Ilúvatar knows all of it.)