Ciao, le code di invio come sono popolate?
m.

Beh, potresti creare un webservice con un servizio
StoreReceivedMessage
che viene invocato dal tuo server SMS alla ricezione di un messaggio e memorizza tale messaggio su database.

Poi un servizio
QueueNewMessage
che popola la coda dei messaggi da inviare con un nuovo SMS.

Infine un terzo servizio
CheckMessages
che ritorna tutti messaggi

Poi con questi 3 webmethod esposti puoi fare ciò che vuoi: pilotare il server SMS da una webapp, da uno smart client, ecc.ecc.ecc.

Questo risponde alla tua domanda?
m.

Beh, allora sicuramente il nocciolo della questione non sta tanto nel webservice, quanto su come gestisci l'invio messaggi dal server SMS, che utilizza la code.

Solo che IMHO non è banale impostare il tutto come chiedi, visto che a questo punto hai bisogno di stabilire una connessione tra processi (server SMS - Web Server). Il modo migliore per farlo è esporre dal tuo server SMS un servizio .NET Remoting (visto che sei vincolato alla 2.0, altrimenti avresti potuto usare WCF) e utilizzarlo per consentire l'invio sincrono di un messaggio, con un valore di risposta che ti indica se è stato effettivamente preso in carico. In questo modo il web service che esponi all'esterno, per soddisfare la richiesta di invio di un messaggio può prima tentare la carta dell'invio sincrono e, in caso di fallimento, accodare il messaggio.

.NET Remoting non è una tecnologia banalissima da apprendere, se non la conosci già è dura da spiegare in un forum.

Ti consiglierei pertanto di spulciare un po' di blog/documentazione MSDN e dare un'occhiata per verificare se fa al tuo caso.

m.