I basically agree with Miki with slight clarification. The main element of a binding contract is offer and acceptance (plus a little thing known as consideration).
But you also need to be able to carry the burden of proof, both as to the existence of the offer and acceptance and as to the actual terms of the contract.
As he noted, enforcing an oral agreement can be difficult both in proving that there was an offer and acceptance and in proving what were the contract's substantive terms.
However, the same can be said, to a somewhat lesser extent, of some of the other forms you mentioned. An exchange of email can certainly create a contract but the exchange may also contain extraneous matters and depending upon the wording of the response, the acceptance may be ambiguous.
For that reason, I still prefer a physically signed contract that contains all of the terms and makes it clear that any discussions or "promises" not contained in the written document are NOT part of the contract. I don't require a mailed copy, however. A scanned PDF of the signed copy is enough for me. Yes, there still might be some argument of whether the signature was indeed the signature of the party I am trying to be bound, or perhaps even a real signature that was copied and inserted into the document. I think that would be very rare - it has never happened to me. A party could contest even a mailed original unless it was signed in front of a notary. You can only do so much.