[Boromir88]

Their man "essence" was still there...so once they died, in being controlled souls, I would think they would be tried. Whereas with Sauron, he was the controller of the evil...so he was turned away.~Mathew

Well Sauron's spirit had become earthbound after the sinking of Numenor, and after the Ring's destruction he was unable again to take a physical form and his spirit would just 'roam the earth.' The Ainur can become earthbound meaning they lose the ability to change their form (as Sauron did) or the ability to construct a new form after they die (as what happens with the Balrogs, and eventually to Sauron when the ring is destroyed). Typically those who commit evil deeds are prone to becoming earthbound.

But, as far as I know this only applies to the Ainur who were the one's able to inhabit and construct other bodies.

There existance in Middle-earth was because of the Ring, Gandalf says that Sauron's power was tied in them:

’You cannot destroy Ringwraiths like that,’ said Gandalf. ’The power of their master is in them, and they stand or fall by him.~The Ring goes South

And I think we have to accept Gandalf's words because when the Ring is destroyed:

And into the heart of the storm, with a cry that peirced all other sounds, tearing the clouse asunder, the Nazgul came, shooting like flaming bolts, as caught in a fiery ruin of hill and sky they crackled, withered, and went out.~Mount Doom

But as far as what happens to them afterwards, always seems to be the big question mark. Logic tells us just as the spirits of Men do, will go to the halls of Mandos and wait there for a period then go out of the Circles of the World.

However, I find something Gandalf says to be interesting:

'You cannot enter here,' said Gandalf and the huge form stopped. 'Go back into the Shadow that is ready for you! Go back! Fall into the nothingness waiting for you and your Master. Go back!~The Siege of Gondor

I think this can be taken a few different ways. Is Gandalf telling the Nazgul to 'go back into the Shadow'...shadow meaning simply go back into the darkness...the nothingness. Or is he telling the Witch-King to die and go into the Void which is awaiting him and Sauron?

If that is the case, then that offers another possibility for the fate of the Nazgul, but I fear raises more baffling questions. The Witch-King was different than the rest of his Nazgul brethren, he was granted extra demonic force in the battle of Pelennor Fields by Sauron, the other Nazgul were not. So would this only apply to the Lord of the Nazgul. And also, we have to question is Gandalf even right about the Witch-King's fate?