Why wouldn't reputation help with this problem? users will have to start small to develop their reputation, but doing so will allow users more trust.
There are ways of doing things that don't involve guns - and that's ultimately what government relies on.
(I thought libertarians were in favour of gun-based dispute resolution systems?)
As for libertarians, you clearly don't understand at all. They want to avoid systems of conflict resolution that depend on violence; that's their whole point. Their obsession with trade, contracts and money arise from their view that those are voluntary ways of interacting.
If a provider can get away with scamming people, without any sort of true repercussions other than a reputation hit, then the rate of "long cons" will probably increase by a lot.
From an anecdotal perspective, I used to be involved in gray markets like trading and selling MMO accounts. Generally there would be no repercussion for scamming the other party; the MMO companies forbade the trade, payment providers don't care, and the government doesn't really recognize it as a real transaction.
These markets had a deeply ingrained reputation system tied to the message board, but escrow was also very common. Many people would offer their services as middlemen to provide escrow for trades, but over time there became an alarmingly high number of middlemen who would properly handle dozens or even hundreds of trades, then scam both parties simultaneously once they came across the biggest transaction of their life. No repercussions came to them; they just stopped being middlemen and had fun with their treasure.
These kinds of examples show that reputation, cryptographic authentication, proof of payment, payment irrevokability, and plain man-in-the-middle escrow combined are still not enough to actually prevent fraud in many cases.
There are some examples of 2-man escrow systems out there using Bitcoin, though, which is far more promising. That prevents any one party from scamming the other 2. The remaining problem, which I imagine will never be solved, is the vendor proving or the buyer disproving that the vendor gave the goods or services that were asked for.
This is impossible with a Bitcoin escrow contracts since 2 of the 3 parties need to agree to unlock the funds, and where to send them.
And this is a perfect example of something that was literally not possible before Bitcoin (well, I suppose it could be done with some elaborate scheme with physical vaults and keys, but certainly not on the internet)
Theoretically people weren't supposed to store their bitcoins in an exchange like MtGox either but here we are today with this mess. The bitcoin protocol and best practices suggest a lot of actions that just don't work due to human nature