The only way to have two different WCF clients, i.e., proxies, reference the same instance of your WCF service is to use InstanceContextMode=InstanceContextMode.Single. This is a poor choice if scaling is an issue, so you want to use PerCall if you can.
When you use PerCall, each CALL to the WCF service gets its own WCF service instance. There's no sharing of the service instance, but that doesn't mean that they don't share the same back-end storage (e.g., database, memory, file, etc.). Just remember, PerCall allows each call to access your WCF service simultaneously.
The ConcurrencyMode setting controls the threading model of the service itself. A setting of Single restricts all of the WCF service instances to running on the same thread. So if you have multiple clients connecting at the same time, they will only be executed one at a time on the WCF service side. In this case, you leverage WCF to provide synchronization. It'll work fine, as you have seen, but think of this as having only macro-level control over synchronization - each WCF service call will execute in its entirety before the next call can execute.
Setting ConcurrencyMode to Multiple, however, will allow all of the WCF service instances to execute simultaneously. In this case, you are responsible for providing the necessary synchronization. Think of this as having micro-level control over synchronization since you can synchronize only those portions of each call that need to be synchronized.
I hope I've explained this well enough, but here's a snippet of the MSDN documentation for ConcurrencyMode just in case:
Setting ConcurrencyMode to Single instructs the system to restrict
instances of the service to one thread
of execution at a time, which frees
you from dealing with threading
issues. A value of Multiple means that
service objects can be executed by
multiple threads at any one time. In
this case, you must ensure thread
safety.
EDIT
You asked
Is there any performance increase, then, using PerCall vs. Single when using ConcurrencyMode.Single? Or is the inverse true?
This will likely be service dependent.
With InstanceContextMode.PerCall, a new service instance is created for each and every call via the proxy, so you have the overhead of instance creation to deal with. Assuming your service constructor doesn't do much, this won't be a problem.
With InstanceContextMode.Single, only one service instance exists for the lifetime of the application, so there is practically no overhead associated with instance creation. However, this mode allows only one service instance to process every call that will ever be made. Thus, if you have multiple calls being made simulateneously, each call will have to wait for the other calls to finish before it can be executed.
For what it's worth, here's how I've done this. Use the PerCall instance context with Multiple concurrency. Inside your WCF service class, create static members to manage the back-end data store for you, and then synchronize access to these static members as necessary using the lock statement, volatile fields, etc. This allows your service to scale nicely while still maintaining thread safety.