It seems like it would have been much faster and they probably would have caught Frodo before he was alerted, no?
The answers might end up being opinion based but to me it seems they did this to be more stealthy.... Remember that the Ring Wraiths looked more like cloaked figures when riding the Horses which seemed to me to be far less alarming then hooded guys riding giant Fellbeasts towards The Shire...
If they did try to go after The Shire on these beasts, there would have been reports of seeing them going towards there which would have led to Gandalf trying to get Frodo and the company out of there even faster... Heh maybe he would have even used his giant Eagles to begin with...
I also noticed this...
According the the LOTR Wikia on them
It seems that the Fellbeasts were not introduced until after the horses were gone...
When the Nine Nazgûl (the Ringwraiths) were thwarted at the Ford of Bruinen near Rivendell, they were riding coal-black horses. Those steeds were destroyed in the flood caused by Elrond's intercession that vanquished the Nazgûl as they pursued Frodo. When next the Nazgûl took form their steeds were these winged creatures, ancient, natural creatures whose origin and appearance were told by Tolkien in the novel The Lord of the Rings, most clearly in his description of the one ridden by the Lord of the Nazgûl (the Witch-King) at the Battle of the Pelennor Fields.
A quote from the LOTR book says :
And behold! It was a winged creature: if bird, then greater than all other birds, and it was naked, and neither quill nor feather did it bear, and its vast pinions were as webs of hide between horned fingers; and it stank. A creature of an older world maybe it was, whose kind, lingering in forgotten mountains cold beneath the Moon, outstayed their day, and in hideous eyrie bred this last untimely brood, apt to evil. And the Dark Lord took it, and nursed it with fell meats, until it grew beyond the measure of all other things that fly; and he gave it to his servant to be his steed.
So perhaps after the original steeds were destroyed Sauron created the Fellbeasts for his Ring Wraiths...
This is all described in the essay entitled The Hunt for the Ring published in Unfinished Tales. All supplied quotes are from that source.
At first the intention was indeed to be stealthy, because Sauron did not want the Wise (i.e the Elves and Istari) to know what he was up to:
Yet this weakness they had for Sauron's present purpose: so great was the terror that went with them (even invisible and unclad) that their coming forth might soon be perceived and their mission be guessed by the Wise.
From there they went invisible through Rohan, passed the Sarn Gebir and the Nazgul of Minas Morgul met up with the Nazgul of Dol Guldur.
This was (it is thought) about the seventeenth of July. Then they passed northward seeking for the Shire, the land of the Halflings.
The last point is important here: at this stage the Nazgul did not yet know where the Shire was.
From here they passed north up the Anduin and began searching, finding the old Stoor villages (presumably those formerly inhabited by Gollum's people) and their best guess at the time was that the Shire was somewhere near or even within Lórien:
They were told also by Khamûl that no dwelling of Halflings could be discovered in the Vales of Anduin, and that the villages of the Stoors by the Gladden had long been deserted. But the Lord of Morgul, seeing no better counsel, determined still to seek northward, hoping maybe to come upon Gollum as well as to discover the Shire. That this would prove to be not far from the hated land of Lórien seemed to him not unlikely, if it was not indeed within the fences of Galadriel. But the power of the White Ring he would not defy, nor enter yet into Lórien.
From here they continue searching north and finding nothing, until they meet messengers from Mordor; here we learn that Sauron had found out about the dream-prophecy in Gondor, Boromir's leaving, Saruman's deeds and capture of Gandalf. Now Sauron panics and orders the Nazgul to Isengard:
From these things he concluded indeed that neither Saruman nor any other of the Wise had possession yet of the Ring, but that Saruman at least knew where it might be hidden. Speed alone would now serve, and secrecy must be abandoned.
Yet again, they still don't know where the Shire is, but on the advice of Saruman (who did know but didn't tell them) they search Rohan for Gandalf, come across Wormtongue, and from him they finally learn the general direction it lies in:
Spare me! I speak as swiftly as I may. West through the Gap of Rohan yonder, and then north and a little west, until the next great river bars the way; the Greyflood it is called. Thence from the crossing at Tharbad the old road will lead you to the borders. 'The Shire,' they call it.
Finally some time past Tharbad they come across some fugitives and learn from one of them (who also turned out to be a servant of Saruman's) where it is:
One of them had been used much in the traffic between Isengard and the Shire, and though he had not himself been beyond the Southfarthing he had charts prepared by Saruman which clearly depicted and described the Shire.
This is the first point at which they actually know where the Shire is; they did not know before then and had to search the various lands they travelled through for it, and - of course - travelling back to Mordor to pick up some Fell-beasts at this late stage would just incur further delays.
So to summarise:
- At first they wanted to be stealthy.
- When Sauron learns what's going on he panics and they abandon stealth.
- And all this time they do not actually know where the Shire is until they are almost right at it's borders.
- Flying directly to the Shire is impossible because they don't know where it is.
- They needed to conduct a careful search on the ground, as well as waylay travellers and obtain information from them, both of which would have been difficult if not impossible if flying.
- The initial need for stealth was not abandoned until the Nazgul were far out of Mordor.
I think Sauron and the Nazgul were not ready to show themselves in entirety. They favoured stealth over a brazen show of strength. Probably Sauron was doubtful as to whether any of his adversaries knew about the Ring. So, such a venture would have alerted them to its existence or so he felt, which is why he sent them as Riders dressed in Black. Remember they have a palpable aura of Black magic around them.
We can provide four conclusions, first one: Possibly the Nine themselves weren't ready or strong enough to ride the Fell beast yet.
The Nine were physically weaker at first (in Fellowship of the Ring) and also their aura was weaker.
They were surrounded by an aura of terror, which affected all living creatures; their aura (called the Black Breath) could be toxic to those hapless enough to come near them.
We could clearly see that when Gandalf was fighting them of on Weathertop and when Aragorn drove them away with two burning sticks. This would prove impossible later in the books as the Nine became even more powerful then they previously were.
...they would become vastly more powerful. However, it is unclear as to how. However, as Sauron's strength grew through the books, the Nazgûl became obviously more powerful. In the Fellowship of the Ring, the Nazgûl's cries were simply unnerving to the hobbits (this may possibly be explained because it was important that the Hunt of the Ring remained in secrecy so they might have diminished their auras, and they did not have the rings of power), and they appeared to be physically weak, as five of them were driven off by Aragorn with two burning sticks. Additionally, Gandalf the Grey managed to hold off the entire Nine single handedly on Weathertop. In The Return of the King however, their cries are powerful enough to send all but the most stout-hearted of Gondor's defenders into a state of helpless terror, and the Witch King in particular has become so powerful that he is a match for Gandalf the White (which of the two is the more powerful is not revealed).
The second conclusion we can provide is that Sauron and the Nine wanted to keep their task as secret as possible. This in many ways would be logical as they took on a disguise as riders in black on black horses. It would have been too obvious if they were flying around on Fell beasts, they couldn't have easily stopped to ask for directions. Imagine popping round the garden on a flying beast and spreading terror. Anyone who saw a Fell beasts would surly have been struck with fear and terror, the word would have quickly spread around and so would have Saurons intentions. Those horses were enhanced and twisted by evil, they could ride them to no end. Handy even to a wraith.
(this may possibly be explained because it was important that the Hunt of the Ring remained in secrecy so they might have diminished their auras, and they did not have the rings of power)
One other major use of the Fell beast was spreading Fear. From the very beginning, Fell Beasts are terrifying creatures; combined with a Nazgûl's screech
Additionally, Fell beasts are a weapon themselves, a powerful war instrument that isn't just bread as a simple mount, a transport beast.
Third conclusion is that simply the Fell beasts weren't ready to be ridden just yet. For some unknown reason maybe the beasts themselves weren't strong enough to carry out the task, but as Sauron's powers grew, so did their strength. For as we know the strength of the Nazgul grew with Sauron's powers.
Forth conclusion is that they underestimated the task of bringing the One Ring back to Mordor. They thought that a hobbit would pose as no threat to the task at hand, which didn't prove as easy since they lost their horses in the flood which Elrond and Gandalf made possible. Then the Nine walked back to Mordor where they received improved new mounts that wouldn't stop them at anything, the Fell beasts.