<p>When working with WCF services, is it better to create a new instance of the service every time you use it?  Or is it better to create one and re-use it?  Why is either approach better?  Is it the same for asynchronous proxies?  </p>

There is a corollary here to Server Activated Objects in .NET Remoting (one of the technologies that is replaced by WCF), which have two modes, "Single Call" (stateless) and "Singleton" (stateful).
The approach you take in WCF should be based on your performance and scaling requirements in conjunction with the needs of your consumers, as well as server-side design constraints.
If you have to maintain state between calls to the service, then you will obviously want to have a stateful instance, but if you don't you should probably implement it so that it is static, which should scale better (you can more easily load balance, etc).