How does .Net Web service handle request from multiple clients

[Tiro]

Hi,
I am trying to understand how does .Net Web Service handle requests for
multiple clients simultaneously.

Here is what I am trying to achieve.
I have created a web serive that search database based on client
request. Client submits query string.

Issue:
If I try to access web service from 2 clients simultaneously using
different query, it gives same results.

Example: (If initiated at same time)
Client - 1
Search term - IL
Result from Web service: full name is Illinois

Client - 2
Search term - WI
Result from Web service: full name is Illinois ( I am expecting "full
name is Wisconsin")

How does .Net Web Service handle multiple clients?
Is there good documentation/Examples/code samples that will help me?

Thanks