Different people will define “free” differently, but, generally, you can say that a free market is one where price operates independently of anyone in the market (no one has enough market power to dictate price). Things that can guarantee this are perfect competition, perfect substitutes, perfect information, low barriers to exit and entry; and other things that don’t or can’t exist in reality. To the extent that they don’t, the government can do things to help make the market more free. For instance, it can help enforce contracts; it can decide boundries on contracts (is a market only “free” if there are contract killings?); it can impose taxes to account for externalities from missing markets (pollution; the missing market is “air” i.e. no one owns it); it can bust up monopolies; and so on. To the extent that they can’t, well, of course nothing is going to help us there.
This is a moral question. It might be, as a matter of empirical fact, that disallowing it helps more people than it hurts, in some kind of total welfare sense. If so, it’s a wise move, economically.
Not necessarily. I am free to travel, even though there are laws regulating travel (e.g., driving on a certain side of the road). The small cost to me in terms of avoiding driving on the other side of the road is far outweighed by the benefit to me of ease of travel. Well, ok, I live near Boston, so I must qualify, “…in theory…” 
But seriously, regulating a market is not necessarily the same thing as saying a market is not free. Even the government “interfering” in price mechanisms doesn’t necessarily constitute an unfree market because certain conditions must be met for efficient pricing to obtain and those might not (practically, don’t) exist. For example, insurance is a quintessentially imperfect market from the perspective of individuals. It is hard to price insurance for individuals because the agent has extremely limited information regarding the individual’s behavior which, if the agent had it, would enable the agent to price accordingly as the risks would be known. In a sense, then, insurance markets can only exist imperfectly because of this. To some extent, the government can help this (make DMV records available, for example, or enforce penalties for lying about behavior to the agent). So, if it takes government regulation to make a better approximation to a perfect market for insurance, is this more or less “free”?
It would strongly depend on what sort of economic theory you adhere to, as there’s plenty different schools of thought, so my statement is a bit misleading; there isn’t a definition, there are rather several, and several criteria for determining what constitutes “better.” To the extent that people prove things about markets, they lay down technical criteria. For a taste of the kind of assumptions made, take a look at wiki’s page on perfect competition or welfare econonics.
Usually they discuss things like perfect information (everyone knows everything) for mathematical reasons, though of course models exist where people have imperfect information (game theory can be used to model this behavior). I’ve never seen a definition of efficient pricing that didn’t implicitly rule out coercion, but “fraud” is a loose term. For instance, I might fraudulently represent myself to my insurance agent, but that doesn’t mean there’s no way to price insurance at all, it just means that everyone’s rates are a little higher to compensate.
I gave an example above, nobody owns air, so pollution cannot be accurately priced. As for the pair thing, Steven Landsburg gave an interesting example. “…[T]he governor of Colorado… recently spoke amusingly about leaf blowers. He told of going for a walk on an autumn day and watching each Denver homeowner blow leaves into the next homeowner’s yard. He concluded that the problem consists of too many markets – we’d all be better off if nobody bought a leaf blower… The governor was onto something, though: two missing markets can be better than one… [G]iven the fact that there is no market for yards-as-trash-cans [erl: missing market], it can be better to eliminate the market for leaf blowers as well.” [From “The Armchair Economist,” emphasis original] Leaf-blowers of course have legitimate uses besides exploiting your neighbor’s property, so take this as a simplified example of the idea.
That is half of it. The other half of externalities are positive externalities, where the benefits are not directly reaped by the parties involved. Negative externalities mean a good is overproduced (because the costs aren’t accounted for directly) while positive externalities are underproduced (because the benefits aren’t directly realized). Wiki has a great example of a positive externality: beekeeping. How does the beekeeper and the customer seeking honey accurately reflect the benefits of pollinization given to nearby farmers or etc? Maybe we should make more honey!
What I mean by the last part is an elaboration of the answer to your first question. The benefits of a free market are a mathematical fact to the extent that we have made mathematical models of free (and unfree) economic behavior. The promise of the free market is guaranteed in the mathematical models; as we strive for that, we reap the benefits.
Hope this helped.