There are a number of fascinating assumptions on sovereignty and justice in this question. A sovereign entity is one who, in the normal course of events, holds or can enforce a monopoly on force. Justice has always been pragmatized to respect sovereignty. This answer is written from a historical/realistic perspective.
Consider the institutions of high and low justice1. Quoth the wikipedia:
High justice is held by all states and the highest vassals in the European type of feudal society, but may also be acquired by other authorities as part of a high degree of legal autonomy, such as certain cities; which in time often obtained other high privileges originally reserved for high nobility and sometimes high clergy. Other such privileges could include a seat in a diet or a similar feudal representative assembly, before the third estate as such even aspired to such 'parliamentary' representation, or the right to mint coins. These privileges indicating its so-called liberty was an 'equal' enclave in the territorial jurisdiction of the neighboring feudal (temporal or ecclesiastical) Lord, sometimes even extending rather like a polis in Antiquity.
[Low Justice] is the level of 'day-to-day' justice, minor cases generally settled by limited fines or light corporal punishment. It is always included in the jurisdiction of the High and Middle Justiciarians, but also by many petty authorities, including many domanial proprietors, who sat in justice over the serfs, tenants, et cetera on their land, or rather assign a steward or the likes to do so for him, or allow a form of jury trial.
There are absolute pragmatic reasons for the existence of these different levels of "justice." The most fundamental is the "who's going to arrest that huge bugger with a sword, then?" Low justice represents the ability to hold a monopoly of force over a subset of the populace (those poor schmucks who can't afford shiny armor, horses, and very very shiny swords.) High justice, being a thing of nobles, means that the majority of nobles could indeed have a monopoly on force (due to the feudal system) and effectively go to war with whomever broke High Justice. As this was an expensive proposition, only the most serious of crimes were listed here.
People exempt from the monopoly of force (in a Hobbsean sense) are sovereign. The best illustration of that is from Stephenson's Snow Crash (caution, harsh language):
"Well, we're not saying it's him," Squeaky says. "But! need to know if this
character" -- he nods at the corpse -- "might have done anything that would have
made Raven feel threatened."
"What is this, group therapy? Who cares if Raven felt threatened?"
"I do," Squeaky says with great finality.
...
"What the f*** did you think you were doing, a****e?" Squeaky says, so pissed that Hiro steps away from him.
"That f****r ripped us off -- the suitcase burned," the Crip mumbles through a mashed jaw.
"So why didn't you just write it off? Are you crazy, f*****g with Raven like that?"
"He ripped us off. Nobody does that and lives."
"Well, Raven just did," Squeaky says. Finally, he's calming down a little. He
rocks back on his heels, looks up at Hiro.
...
Hiro is mortified by this idea. "Is that why everyone was telling me not to
f*** with Raven? They were afraid I was going to attack him?"
Squeaky eyes the swords. "You got the means."
"Why should anyone protect Raven?"
Squeaky smiles, as though we have just crossed the border into the realm of
kidding around. "He's a Sovereign."
"So declare war on him."
"It's not a good idea to declare war on a nuclear power."
"Huh?"
"Christ," Squeaky says, shaking his head, "if I had any idea how little you knew
about this s***, I never would have let you into my car. I thought you were
some kind of a serious CIC wet-operations guy. Are you telling me you really
didn't know about Raven?"
"Yes, that's what I'm telling you."
"Okay. I'm gonna tell you this so you don't go out and cause any more trouble.
Raven's packing a torpedo warhead that he boosted from an old Soviet nuke sub.
It was a torpedo that was designed to take out a carrier battle group with one
shot. A nuclear torpedo. You know that funny-looking sidecar that Raven has on
his Harley? Well, it's a hydrogen bomb, man. Armed and ready. The trigger's
hooked up to EEC trodes embedded in his skull. If Raven dies, the bomb goes
off. So when Raven comes into town, we do everything in our power to make the
man feel welcome."
Hiro's just gaping. Y.T. has to step in on his behalf. "Okay," she says.
"Speaking for my partner and myself, we'll stay away from him."
At the end of the day, most adventuring parties are Raven. They've got poor impulse control and a nuke on their mounts. Town authorities will almost certainly try their best to be as respectful as possible to the people with the nuke, recreating the idea of High Justice. When the heroes become sufficiently disruptive to the incomes of other sovereign individuals such that they are willing to go to the expense of functionally going to war, then adventuring parties fight.
The fundamental concept is this: you can only police that which you have the power to police. While this concept is alien to modern thinking, it is everywhere to be found in the past (and why crossbows were so very annoying to knights).
Here are some traditional forms of dealing with this problem.
Noblesse Oblige
A tradition of honor
This really is the best solution for the peasants. For nobles to self-police such that they don't do these things. This requires a high number of adventuring groups, but with a decent number, getting a reputation for poor impulse control will eventually sour important deals. This then creates negative feedback on that impulse control and creates a sense of tradition. Once most parties subscribe to this, then there will be significant social pressure on those who don't. This also applies to mages and all other sovereign entities.
Priests exist as professional talkers-to-nobility
One of the really important roles of Rome in the past has been as "talkers-to-nobility." They tried to steer the impulses of nobles towards useful pursuits by inventing the idea of chivalry from what amounts to whole cloth. This was only middling effective, but the idea is useful: super-national institutions can be highly effective as ways of transmitting grievances, guidance, and advice to sovereign entities. On a practical level, if a member of the party isn't behaving, a priest or equivalent will usually plead with them. It's important that the individual pleading is not part of the local power structure, but affiliated with it.
Threat of overwhelming force
Here is the "so declare war on them" set of options. First, the overwhelming force must exist. Which means that the leaders of the land (as ex-adventuerers) must care enough about the problem to be willing to go to war with the mage/adventuring party. On borderline cases however, the threat is enough.
Threat of overwhelming force
While this tends to be couched in nicer terms, it boils down to someone in a position of power noting that if this keeps up, there will be pain. This threat will be phrased differently in different lands, but sovereigns who refuse to employ and enforce their monopoly on force ... cease being sovereign. The idea of "consent of the governed" is one of those modern concepts that just doesn't map to before the enlightenment.
Parole
Quoth the wiki:
Parole is "the agreement of persons who have been taken prisoner by an enemy that they will not again take up arms against those who captured them, either for a limited time or during the continuance of the war".
Again, this is using war interactions since those are the only ones possible between sovereign entities. This is the other side to the threat. Where if a mage/party is doing something naughty, and are caught, they are asked to give their Parole. What this boils down to is: "We don't want to go to the expense of killing you, and you don't want to die. So promise you won't do X again, and we'll both be happy, OK?"
Declared Outlaw
Outlaw is a fascinating term. It comes from the time where people could not be hauled up before courts because of a depressing lack of man-power in the "justice system." The act of declaring someone "outlaw" requires that a nation have a set of laws in place (so it's rather more modern than parole). However, it simply notes that such and such an individual is "outside the law" and therefore enjoys none of the protections of the law. The subtext is: "And it'd be nice if someone killed him." The threat of this is actually quite nasty, since there's no penalty (beyond the individual's responses) for defrauding, murdering, etc.. the individual. It also signals that there's free and legit loot to be had to other adventuring groups.
Hold people/things forfeit
Hostage taking is an absolutely legal aspect of warmaking. It's generally a lot easier to secure whatever you hold hostage to good behaviour than the individual or party themselves. The trick for it to be legal is that it must be part of a contract, functionally, between the two parties. Illegal hostage taking generally doesn't make the contract for good behaviour beforehand. This doesn't work very well.
Hostages
Better as a longer-term solution, most feudal governments already have large administrations designed for the keeping, education, and general preservation of "allied" hostages. The "page" system may have roots here, giving hostage youngsters a chance to participate in the court of their sovereign. For a fantasy game, gifts of quarters in the palace of whomever wants to try to be sovereign over the party are a very interesting payment, especially with the communicated subtext that their families will be well cared for. So long as the adventuring party doesn't do anything foolish like wipe out a town. As part and parcel of this, aristocrats will be performing their traditional job (more detail) in D&D games \footnote{Keeping adventurers happy}. Hostage-to-love as a phrase exists for a reason. Most communities will be actively encouraging their best people to enter into a relationship with these adventurers for all sorts of reasons. Adding a reason to not nuke the community is pretty high up there.
Still, in more pragmatic and larger cities, they may ask for members of the adventuring party to willingly act as hostages (excellent for a city-game when one of the members can't make it.) While this is unlikely, it may be the case in a city on the edge, during or close-to war, or other tense times. It's also a great way to completely subvert the players' expectations of adventure to allow the people who volunteered to be hostage to be well taken care of, given anything they want to drink, and then returned unharmed, with all of their gear well cared for.
Bail or a deposit
In most cities, it's a lot easier to lock coin away than it is members of an adventuring party. A city that does this on a regular basis will have established a fiat currency and insures that its shops only accept that currency. At the gates, magic users and party-members will be asked to place a deposit (that they will get back, with interest) forefit on their good behaviour. They will then be able to use this deposit to pay debts incurred in the city. Done well, both the adventurers and the city prosper. It would also make a fantastic side-quest to be commissioned to hunt down a rogue who had the audacity to try to steal from The Vaults. (or to steal from said vaults...)
Summary
This is not a new problem. Magic users and adventuring parties are, in a realistic world, sovereign entities unto themselves. Sane sovereigns recognise this and deal with them accordingly. The small crimes are written off and the larger crimes cause limited war. While here are magical means of neutralising magic, they belong in a much more modern game that provides for an efficient police force for everyone. For clues to how this works, take a look at the Powers comic, a police procedural dealing with enforcing the laws against superheroes.
1 Also a
fascinating novel by Jerry Pournelle, remarkably apposite to the discussion.