ASP.NET - Servicios Web Asíncronos para expertos

Hola buenas tardes tengo una duda en referencia al funcionamiento de los servicios Web.
Yo sé que las "llamadas" que se hacen a un servicio Web se pueden realizar de forma asíncrona pero....... ¿Es posible tambien que el servicio web se ejecute o ejecute su tarea de forma asícnrona?.
Por ejemplo yo tengo una base de datos de access con cien registros y en cada registro hay un número de teléfono. Realizo un bucle y rerorro los cien registros, cada vez que se posiciona sobre un registro captura el telefono y realiza la llamada asíncrona a el servicio web, el servicio web con ese telefono manda un mensaje sms al telefono que le hemos enviado y a los cinco segundos aproximadamente me envia con return si el mensaje ha sido ok o ko es decir si lo ha mandado correctamente o incorrectamente.

Claro recorrer el bucle de cien registros y llamar al servicio web de forma asíncrono tarda unos 24 segundos. Pero una vez que termina de recorrer la base de datos, tardo 5 segundos por cien mensajes unos quinientos segundos, es decir diez minutos en tener todos los resultados de los cien mensajes procesados por el servicio web.

Por eso yo pienso que la llamada al servicio web es asíncrona, pero cuando el servicio web tiene que procesar todas las peticiones lo realiza de forma síncrona es decir uno detras de otro.

Por favor decidme si eso es así o si por lo contrario tambien existe alguna manera de poder hacer que el servicio web en sí trabaje tambien de forma asíncrona y así reducir considerablemente el tiempo de espera.

Gracias un saludo

Creo que te puede servir que programes la llamada al SMS usando un Thread

Yamil no me dejes a medias por favor, me comentas en tu email que me podía servir usar un thread para llamar al sms pero ¿como puedo implementar un thread en un servicio web?. Abajo te muestro el codigo que tiene mi servicio web al cual llamo desde un formulario web de forma asíncrona, pero yo pienso que este servicio web funciona de forma sincrona es decir una peticion de envio detras de otra es decir un mundo de tiempo esperando para tener todos los resultados.
La funcion mensaje recibe del formulario web el telefono , el texto que se mandara en el mensaje sms y el dorsal de un corredor, entonces mediante sms.send envia el mensaje y con sms.getresult recupera el valor de ok o ko según se halla enviado el mensaje bien o mal, pero ese proceso tarda cinco segundos por mensaje.
Por eso yo no se que hacer para que sea mas rapido es decir si se puede hacer que este servicio web funcione de forma asíncrona y mande mensajes sms sin esperar a recibir la peticion del primer mensaje.
O como tu dices mediante hilos o threads.
Por favor dame una idea de como mejorar el codigo abajo reseñado.

<Global.Microsoft.VisualBasic.CompilerServices.DesignerGenerated()> _
Public Class WebService
Inherits System.Web.Services.WebService
<WebMethod()> _
Public Function MENSAJE(ByVal telefono As String, ByVal texto As String, ByVal dorsal As String)
Dim SMS As New SMSCOM.SMSSend
SMS.setAccount("prueba.com")
SMS.setPwd("1234")
SMS.setText(texto)
SMS.setTo(telefono)
SMS.Send()
Dim GETRESULT As String = SMS.getResult
Return GETRESULT
End Function
End Class

Un saludo gracias.

yo lo que haria es que el web service solo reciba peticiones de envio de mensaje,
ej: insertaria en una tabla mensajes.

luego crearia un servicio windows, que este sensando la bd para ver si existen peticiones de mensajes y los envio.

Gracias Willian pero no entendí bien la respuesta, veamos tu me dices que el servicio web lo único que haga es que almacene en una tabla los mensajes para enviar y posteriormente desde un servicio windows los mande.
Pero aun así tardaria incluso mas tiempo, por ejemplo imagina que yo ya en una base de datos de access ya tengo cien registros con cien telefonos los cuales quiero enviar con un mensaje determinado. Si eso lo hago por ejemplo con visual basic .net tendría que recorrer la tabla de los mensajes desde el principio hasta el fin y que yo sepa la base de datos de access la recorre de forma síncrona y no asíncrona es decir se posiciona en el primer registro lanza el mensaje y tarda unos ocho segundos mas o menos en recibir la respuesta de si lo ha enviado bien o mal, luego pasa al siguiente registro y hace lo mismo y así hasta el final, es decir no se mueve de registro en registro y va lanzando los mensajes sin esperar la respuesta del mensaje anterior.
No se si es eso lo que querias decirme o existe alguna forma de que trabaje de forma asíncrona.
Gracias Willian ayudame porque me he quedado bloqueada .
Saludos.