Uma maneira mais fácil seria autenticar na primeira consulta, construir um registro de sessão no lado do servidor contendo o endereço IP remoto e um token que você fornece ao cliente como um authToken. Em seguida, faça com que o cliente passe esse authToken em consultas futuras. Este authToken deve corresponder aos dados internos da sessão que você mantém sobre o cliente, mas permitiria evitar ter que fazer viagens de ida e volta ao banco de dados apenas para fazer a autenticação.

Dito isso, @Marcus Adams tem um bom ponto abaixo em relação à apatridia. Há pessoas por aí empurrando todos os tipos de modelos de segurança SOAP . WS-Security é o estado atual da arte, aqui. Todos eles funcionam colocando informações de autenticação no cabeçalho SOAP - afinal, é por isso que uma mensagem SOAP contém um cabeçalho e uma parte do corpo.