It seems that the bad guys were either banished, killed or just ran wild causing trouble until they were 'dealt with'. Were there any jails in Tolkien's legendarium?
The Shire has Shirriffs and had Lockholes during the Scouring, but that's something of an exception being a more "modern" society. No doubt other "modern" parts of Middle-earth have a similar setup; Dale and Lake-town spring to mind, although I'm not aware of any evidence.
We also know that Thranduil kept prisoners (from his people's treatment of Thorin's company, and of Gollum), and no doubt the same would apply for other similar Elven cultures (but this can be a dangerous assumption: see further below).
The rest of Middle-earth would doubtless have a more primitive justice, as befits it's more ancient-world feel. Think Hamurrabi rather than the Kings Justice doing the rounds.
There's one interesting case in the legends of the First Age that nicely illustrates how primitive even High-elven justice can be. The Dark-elf Eol, after poisoning and killing the King of Gondolin's sister, was taken before the King and sentenced to be thrown off a cliff:
Therefore when Eol was brought before Turgon he found no mercy; and they led him forth to the Caragdur, a precipice of black rock upon the north side of the hill of Gondolin, there to cast him down from the sheer walls of the city ..... Then they cast Eol over the Caragdur, and so he ended, and to all in Gondolin it seemed just.
No appeals, no niceties, just immediately dragged off and thrown from the edge. And this is one of the most civilized, "wisest" societies that Middle-earth has known.
Middle-earth hosts various prisons, with most strongholds and cities having one.
There is significant precedence for the existence of prisons/lockholes/dungeons in Middle-earth. They have been mentioned throughout the works with people being imprisoned for various reasons by people of a multitude of relationships. Below is a list of prisons that have been mentioned.
One of the earliest mentions of prisons in Tolkien's published works comes from The Hobbit, as Thorin and his company travel through Mirkwood, they are captured by the Woodland Elves and imprisoned.
The king’s cave was his palace, and the strong place of his treasure, and the fortress of his people against their enemies. It was also the dungeon of his prisoners. So to the cave they dragged Thorin — not too gently, for they did not love dwarves, and thought he was an enemy.
The Hobbit - Chapter VIII: Flies and Spiders
“It is a crime to wander in my realm without leave. Do you forget that you were in my kingdom, using the road that my people made? Did you not three timespursue and trouble my people in the forest and rouse the spiders with your riot and clamour? After all the disturbance you have made I have a right to know what brings you here, and if you will not tell me now, I will keep you all in prison until you havelearned sense and manners!”
ibid. - Chapter 9: Barrels out of Bond
The dungeons of King Thranduil are again mentioned in the Lord of the Rings, when Gandalf makes mention of Gollum's imprisonment in said dungeons.
The Wood-elves have him in prison, but they treat him with such kindness as they can find in their wise hearts.’
Fellowship of the Ring - Book 1, Chapter II: Shadow of the Past
The Goblin King
The Goblin King (and other Goblins) were known to keep prisoners and slaves to do work for them.
Hammers, axes, swords, daggers, pickaxes, tongs, and also instruments of torture, they make very well, or get other people to make to their design, prisoners and slaves that have to work till they die for want of air and light.
The Hobbit - Chapter IV: Over Hill and Under Hill
The Necromancer (Sauron) was known to keep prisoners. One famous prisoner was the father of Thorin, Thrain. Who was captured after he was given the map to Erebor by his father, Thror.
“Your grandfather,” said the wizard slowly and grimly, “gave the map to his son for safety before he went to the mines of Moria. Your father went away to try his luck with the map after your grandfather was killed; and lots of adventures of a most unpleasant sort he had, but he never got near the Mountain. How he got there I don’t know, but I found him a prisoner in the dungeons of the Necromancer."
The Hobbit - Chapter I: An Unexpected Party
Pippin, either from knowledge of the Last Homely House East of the Sea, or from The Shire, threatened Elrond with stalking the company unless imprisoned in Rivendell or sent home in a sack.
‘Then, Master Elrond, you will have to lock me in prison, or send me home tied in a sack,’ said Pippin.‘For otherwise I shall follow the Company.’
The Fellowship of the Ring - Book 2, Chapter III: The Ring goes South
The Golden Hall of Theoden was known to have prisons, as Éomer was sent there after disobeying orders and threatening Gríma's life:
‘Much,’ said Gandalf. ‘But first send for Éomer. Do I not guess rightly that you hold him prisoner, by the counsel of Gríma, of him that all save you name the Wormtongue?’ ‘It is true,’ said Théoden. ‘He had rebelled against my commands, and threatened death to Gríma in my hall.’
It is said in The Tow Towers, where there had once stood a great tower, Saruman had reshaped it in mimicry of the Dark Tower, adding amongst other things, a prison.
But Saruman had slowly shaped it to his shifting purposes, and made it better, as he thought, being deceived –for all those arts and subtle devices, for which he forsook his former wisdom, and which fondly he imagined were his own, came but from Mordor; so that what he made was naught, only a little copy, a child’s model or a slave’s flattery, of that vast fortress, armoury, prison, furnace of great power, Barad-dûr, the Dark Tower, which suffered no rival, and laughed at flattery, biding its time, secure in its pride and its immeasurable strength.
Just after escaping from Shelob, a note is made by the narrator that Sauron would send his prisoners to her, when he had no use of them any longer.
If now and again Shelob caught them to stay her appetite, she was welcome: he could spare them. And sometimes as a man may cast a dainty to his cat (his cat he calls her, but she owns him not) Sauron would send her prisoners that he had no better uses for: he would have them driven to her hole, and report brought back to him of the play she made.
The Two Towers - Book 4, Chapter IX: Shelob's Lair
A brief vision he had of swirling cloud, and in the midst of it towers and battlements, tall as hills, founded upon a mighty mountain-throne above immeasurable pits; great courts and dungeons, eyeless prisons sheer as cliffs, and gaping gates of steel and adamant: and then all passed.
The Return of the King - Book 6, Chapter III: Mount Doom
Michael Delving (Thanks to Saruman)
After returning to the Shire, the four Hobbits find that it isn't quite how they left it. With Saruman having set up a prison in Michael Delving for the disobedient hobbits. We also know that the Hobbits had Shirrifs, which acted like police and would arrest people.
And then there’s the Lockholes, as they call ’em: the old storage-tunnels at Michel Delving that they’ve made into prisons for those as stand up to them.
ibid. - Book 6, Chapter VIII: Scouring of the Shire.
I've been working on this for quite a while, so I'm going to leave it with just the info from TH and LotR for now and add in more later.
Well the Valar held courts in Aman the Blessed Realm at place called: Mahanaxar the Ring of Doom where they judged the criminal cases and often held councils. We are also told that after spectacular Battle of the Powers (which echoes were perceived by elves at Cuivienen hundreds and hundreds of miles away as great flashes of light and earthquakes) that Morgoth was put to prison meaning into the Halls of Mandos (also chained by the very special, made for that very purpose Angainor, the chain made by Aule, apparently magical).
When someone's imprisoned in the Halls of Waiting, there's no escape (for those who don't know Halls of Mandos are a place for the spirits of the dead of all races, but mortals stay there only for unspecified amount of time until they leave permanently to whatever fate that awaits them, it's also the dwelling place of Vala Namo also called Mandos it has apparently semi material location in Aman in land of Valinor where also all other Powers have their physical dwellings, but Halls of Mandos appear in the same time semi spiritual and they grow over time, possibly there is a connection to the Unseen the spirit or shadow world, second layer of reality besides the visible world, a plane where wraiths and spirits exist and roam freely, as well as there are certain things native to it ,,signs and forms that are hidden to us", ,,things in worlds invisible to mortal men") anyway returning to topic.
We know that Elvenking's Halls in Mirkwood were not only a stronghold, refuge for elves, storage, treasury and royal palace but also dungeon for prisoners (and to add something, don't worry if you ever get to this elven prison, elves treat even their greatest enemies very decently once they capture them :):) ), another prison facilities are of course the great fortresses of the Enemy, Dol Guldur and Barad-dur (nobody ever escaped Barad-dur unless released on purpose or to last trip on death sentence in Shelob's Lair) and there is of course famous Angband the Hells of Iron, where thousands of slaves were performing hard labour, as you can summise those places hardly have anything in common with ,,justice" or ,,law enforcement" unless in twisted minds of their masters. We also know that Eomer was imprisoned in Edoras for threatening Grima, king's advisor, with death in king's presence (so there must have been a dungeon or something similar in the city, maybe even in Meduseld itself), it is also reasonable to assume that other cities or strongholds of various peoples would have facilities for keeping imprisoned criminals. As for general law enforcement in Middle Eaeth that's a different question altogether, we know that wanted criminals can have a price on their heads, they are judged either by local king or other authorities (like great gatherings among people, so called moots like men of Brethil did).