[Feanor of the Peredhil]

Could they have been effective in the "living Middle-earth?" Effective as in being able to kill others from another parallel dimension?

The Witch King is not exactly alive though, is he. Which probably explains why, when boosting his own ego, he didn't say "Fool! No living man can kill the likes of me! Me, the Unstoppable. Me, the Greatest. Me..." You get the idea. The question is not really that of the Witch King being killed, because he's already dead. Or at least, not living.

Far off yet is his doom, and not by the hand of man will he fall

Like Lal said, this prophecy is rather vague. If Glorfindel had said "not by the hand of Man", it would be different. If he'd said "not by the hand of a man", it would be different. If Glorfindel said "Don't bother going after him, there's a pretty blonde chick and a midget who are going to remove him from our plane of existence in the future", I wouldn't have bothered wasting bandwidth.

Of course, this introduces the predestination vs. free will debate into the mix.

And so was it predestined that Eowyn and Merry would manage to be together at that time? Or was it pure dumb luck, and if Merry had smelled pipe-weed at the wrong moment, the world would have to wait another millenia before the right circumstances arose? Was it an exact guarantee that these two would be the ones to defeat the Wikkie (as he was so cutely nicknamed), or was the prophesy loop-holed enough that a dead guy trying to get back into Eru's good graces could fix the problem.

Certainly, one of the weapons of the WK is fear, and he would have been all too aware that it would be unlikely that any man would dare to try and stop him.

The Dead Army also wielded fear. As I recall, that was their primary weapon.

Fea