First of all, I don't think Tolkien would have put a prophecy in his works if it wasn't going to turn out to be true. It would have been completely pointless. I like to think that he had a reason for almost everything he wrote and a prophecy is too big for there not be one.
Also, judging by the Witch-king's reaction, I deduce that this is what he must have been thinking:
- Look at this puny little man trying to stand up to me. (knowing that he could not be killed by a man) (Eowyn says: but no mortal man am I...) Surprise and confusion rush through his mind. Huh, the prophecy didn't say anything about a woman...
By the way, I never thought that the WC didn't know Gandalf's true race. I just thought he was being contemptious because he was so evil, but now that you mention it, him not knowing makes more sense.