I think you don't quite understand how skirmishes and skirmish actions work, Ramingo. Here's a brief rundown:
1) FP chooses which skirmish to resolve.
2) Perform any "at the start of skirmish" actions, with the FP getting the first opportunity to do so, then alternating until both players pass.
3) FP chooses to play a skirmish event, use a skirmish special ability or pass, then the Shadow player gets that same choice. Continue this until both players pass.
4) Skirmish resolves with a winner and loser.
4a) Perform mandatory actions resulting from the skirmish resolving, such as placing a wound(S) on the losing character(S).
4b) Perform optional actions resulting from the skirmish resolving, again beginning with FP and alternating back and forth.
5) FP chooses next skirmish to resolve.
As you can see, Shadow player gets the opportunity to use
Not Easily Destroyed during section 3 of the above list, while The Witch-king's ability is used during section 4b.
Furthermore, The Witch-king's ability can be used only once each time he wins a skirmish. So even if
NED and The Witch-king could be used during the same time frame, it wouldn't make any difference.