Searching the Internet I discovered (there are huge chances that I may be wrong) that this might have to do with the default behavior of DotNet framework which locks the session to the first in first served device:
ASP.NET application to serve multiple requests from a single process
and
Android http connection - multiple devices cannot connect the same server
I suppose that my IIS assumes that the attempt to hit the web service from the second device is another attempt by the same device. I also suppose that it assumes the device to be the same device since it is the same application with the same internal environment hitting the web service and it can't tell that they are two different devices. I tried to reproduce this error and check if I am right by hitting the IP reporting page in IIS from two different tabs of the Mozzila Developer edition browser but it works ok (so I am not sure if it is a session issue). I also found a report that the issue is present only in android devices but it was not clear enough if the server was IIS... The solution mentioned was "incorrect flag on the tcp kernel settings - Reuse connection". Does it tell anything to anyone of you?
If the session lock is indeed the problem is there a solution to make IIS distinguish that there are two devices indeed? Is there a setting in IIS that would change this default behavior of DotNet?
I am sure there is a solution (if indeed the issue is session lock) because I uploaded my code to an on-line server and it works perfect when hitting it from two Android devices. So either it is not a session lock issue or there is a setting that it changes this behavior of DotNet in IIS... Is anyone aware of such a setting?