Frodo in the Tower of Cirith Ungol

[Zigûr]

Originally Posted by Kuruharan

What sort of means might Shagrat have had to send such a message so quickly?

I would imagine that the first message ("prisoner captured at Cirith Ungol"), if it existed, was sent the conventional way, on foot. If it was sent on the 13th it might arrive on the 15th, as I believe Shagrat left on the 14th and arrived on the 16th. Then I imagine that the second piece of news ("prisoner escaped") was not sent by Shagrat at all, but communicated quickly by the means you've discussed (which I also discuss a bit more below). Unlike a message sent on foot, there's time for all of that news-sending to happen on the 15th if it was done by air (or some supernatural means). Then the third piece of news is delivered by Shagrat on the 16th.

Originally Posted by Kuruharan

Another likely possibility is Sauron made use of a kind of fell-beast express for transmitting messages.
[...]
Were the Watchers, perhaps, in some way hooked into a wider "security net" for Mordor where Sauron would be aware if one of the Watchers in the realm was uneasy?

Yes, these were the two possibilities which occurred to me; one possibility is that the hypothetical news sent by foot arrived on the 15th, a Ringwraith investigated and discovered what had happened since, hastily flew back to the Dark Tower with news, and then returned to Cirith Ungol to take command. All this could conceivably have happened before Shagrat reached Barad-dûr. The other I considered is that the alarms of the Watchers revealed that something had gone wrong.

That or, as you say, some kind of telepathic link between Sauron and the Nazgûl, although I'm not sure how much evidence there is for that (and I suspect that there may be evidence to the contrary, as you've also indicated).