I have failed to understand over and over from this MSDN article why should we use it and how does it work:
Let's assume that I have a Service with
InstanceContextMode = InstanceContextMode.PerSession
ConcurrencyMode=ConcurrencyMode.Single
If I have 2 clients for this service and they activate a method in that setrvice at the same time, why should one of them wait until the service finish the other one request?; PerSession + 2 clients = "2" services that each of them have ConcurrencyMode.Single. Where is my mistake?
As for the B part of your question, there is an excellent series of articles about WCF instancing, concurrency, and throttling here:
UPDATE
Check the instance context id, session id, and thread id on the service for each of your client calls and first verify that these are different.
To check instance context id:
OperationContext.Current.InstanceContext.GetHashCode()
To check session id:
OperationContext.Current.SessionId
To check thread id:
Thread.CurrentThread.ManagedThreadId
If they are all different for each client then I cannot explain the problem you are having.