[Michael Wilhelmson]

I was about to say that the Nazgul might not have been powerful enough at the time that they were sent out to find the Ring. The only real record of a Nazgul at the height of its power was during the Arnor-Angmar war, and that war was lost to the army of Gondor even with the Witch-King in charge. I had always assumed that Sauron's and their power was not yet great enough to directly fight, and that they were sent only to seek and capture the Ring from some Shirelings, not to fight in open battle.
But the time frame seems off on this. Not a few months later, the Nazgul were flying, and leading the armies of Mordor into combat. Even with a few distracted and weakened by Gandalf, being afraid of fire and water, hearing the name of Elbereth, being stabbed by a Numenorean dagger, fighting the King of Men himself, in a place of great Mannish and Elvish power, far from Mordor and their master, and being surprised and shocked by all of these events intersecting...there should have been no way that nine immortal phantom warriors could not have found and killed some hobbits and a Dunedain.