[Mithadan]

Gorbag was the captain of the Morgul patrol that, together with the troops from the Cirith Ungol tower, found the unconscious Frodo after the attack by Shelob. The patrol was apparently sent by the Nazgul in Minas Morgul. So the question is how did Barad-Dur communicate with Minas Morgul "quicker than anything could fly"?

Good question. There are two overlapping answers. Clearly, Sauron did not have to send a messenger to Morgul to communicate with the Nazgul. He could speak to them via "other means." Sauron controlled the Nine Rings, and, therefore, the Ringwraiths. In addition, he could communicate or exercise his will over the Nazgul via Osanwe. Until the publication recently of The Nature of Middle Earth (NoME), a significant essay by JRRT, Osanwe-Kenta, was only available in a limited fashion. It was originally published in Vinyar Tengwar in 1998. This essay addresses, among other things, mind to mind communication, primarily what we see at the end of LoTR during the post-war journey back north, when the bearers of the three Elven Rings converse in this manner after the Hobbits have fallen asleep.

Sauron could use Osanwe to communicate directly with the Nazgul, whom he controlled via the Nine Rings. Such a message would be passed on almost instantaneously. Of course, there may have been more mundane methods of communications such as signals, beacons or flags, but Osanwe is the most likely candidate here. Or, in this case, there may have been no direct communication at all. LoTR discusses the Witch King's "unease" when he led his army from Morgul, because he sensed some other "power" in the vale. His unease may have prompted him to dispatch a patrol into Cirith Ungol. Gorbag may have merely been sent without any explanation why.