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:
1-In ServiceContract use the following SessionMode attribute:
[ServiceContract(SessionMode=SessionMode.Required)]
2-In ServiceBehaviour use PerSession attribute as following:
[ServiceBehaviour(InstanceContextMode=InstanceContextMode.PerSession)]
3-And since you are saying that multiple applications are involved in this Service, so use Reentrant property of Concurrency in ServiceBehaviour as following:
[ServiceBehaviour(ConcurrencyMode=ConcurrencyMode.Reentrant)]
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.
Regards,
Gittu