(1) Contracts can work, and having a well drafted agreement with your clients is important. However, you are right that contracts and legal action are not effective in many cases. A contract will not protect you if the amount you are owed is too small to justify the time and cost involved in pursuing legal action. A contract will not protect you if you cannot get jurisdiction over the other party. A contract will not protect you if the other party simply has no money to pay for the services you delivered. However, I still recommend that you have a good contract for those instances in which it makes a difference.
(2) I think in many cases an advance is appropriate. Of course, if you are as unknown to the client as the client is to you, then there is a question of who should trust who. You would be asking the client to trust you with his money before you have shown that you can and will deliver the services you are promising. An alternative, which can be used either with or without an advance, is what is known as progress billing, which is what arthurhcates described.
(3) I agree that going through a freelance site simply to take advantage of the escrow function does not seem like a good solution. Although it does solve the mutual trust issue I mentioned above, I don't believe that introducing a third-party to your client relationship is generally a good idea.
I think that Sagewing is correct when he says "the way to ensure that you always get paid is to find a great clients and do great work." However, the situation is almost never that black and white.
I am in a different profession, but face the same issue. I have many clients who have been clients for more than 20 years. I would never dream of asking one of them for a deposit on a new matter. But I am also always getting new clients. Some of the new clients are well-established businesses with known reputations. I also would not ask those businesses for a deposit.
In many cases, however, new clients are startups or small businesses that are completely unknown to me. From experience, I know that many of them have big dreams but very small pocketbooks. While they have every intention of paying the bill, it is based on their expectation (often unreasonable) that revenues will take off immediately or that their business will bring in money from investors to pay the bills. The only way I have found to deal with the problem is to ask for an upfront payment.
A few weeks ago, I met with a potential client who came as a personal referral from someone who once worked for me. After meeting and discussing his needs, including the potential cost, I asked for a deposit of $500, representing only a very small portion of the expected cost of the project. His response was that he felt that was reasonable and wanted to proceed but said it would take him several days to get the $500 together.
That was a big red flag for me. I would be potentially providing thousands of dollars in services to someone who couldn't even write me a check for $500. I politely, but firmly, revisited our discussion of the cost of the project, emphasizing that I would have to stop work if our fees were unpaid and that there was no value at all in a half finished project. Thankfully, he did not decide to pursue the project, or at least not with me.
There were no outward signs that this client who was referred to me would be a problem payer. Only my request for a deposit saved me from a disastrous engagement.