Yeah, requirements like this comes in case of Services which depend on multiple resources.
I'd suggest you the following points, implementing which you could achieve your desired result:
In ServiceContract use the following SessionMode attribute:
In ServiceBehaviour use PerSession attribute as following:
3-And since you are saying that multiple applications are involved in this Service, so use Reentrant property of Concurrency in ServiceBehaviour as following:
This will help you to avoid any kind of DeadLock.
I'm sure if you could use the above properties efficiently then you would surely achieve your desired goal.