Nar, Sauron assumed a form that could be harmed. He wasn't invulnerable; merely very powerful. How else could Elendil and Gil-Galad have killed him?
The Witch-King was an entirely different kettle of fish.
Gandalf's line about no weapons that could hurt him is a headscratcher and no doubt. Maybe all he meant was
'Try and hurt me 'Gorn, you've no chance!' As in, a boast.
