I read about an small island in northern Sweden that was used for trade between locals and southerners with a simple system of placing items on a given date, leave for a day and then return. If there was any takers there was a pile of stuff next to yours. If you accepted you took that pile and left. If you wanted to barter you either decreased your pile or left it all. Anyhow you then left for a day. When you returned the other side had either made a new bid or taken their stuff back. I believe it was described in the 18th century (possibly Linneaus or one of his pupils) as having been around longer then anyone could remember. This is what I would call a market that was regulated, but without government.
You can also have trade without regulation - for example viking style - but a market implies something a bit more permanent. And then there is regulation.
Bit ot, but the "unregulated market" is an annoying term. A vote for PES is a vote for EPP! A vote for EPP is a vote for PES! Support the coalition, vote EPP-PES in 2009!