You should take a look at the WS-Security and WS-Policy standards. The best way is to have the client application sign all requests (with a private key) and check this signature on the server side.
We use a setup like this, with the following WS-Policy definitions in the WSDL:
<!--Endpoint Policy-->
<wsp:Policy wsu:Id="Endpoint_policy"
xmlns:wsp="http://schemas.xmlsoap.org/ws/2004/09/policy"
xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
<wsp:ExactlyOne>
<wsp:All>
<sp:AsymmetricBinding
xmlns:sp="http://schemas.xmlsoap.org/ws/2005/07/securitypolicy">
<wsp:Policy>
<sp:InitiatorToken>
<wsp:Policy>
<sp:X509Token
sp:IncludeToken="http://schemas.xmlsoap.org/ws/2005/07/securitypolicy/IncludeToken/AlwaysToRecipient">
<wsp:Policy>
<sp:WssX509V3Token10 />
</wsp:Policy>
</sp:X509Token>
</wsp:Policy>
</sp:InitiatorToken>
<sp:RecipientToken>
<wsp:Policy>
<sp:X509Token
sp:IncludeToken="http://schemas.xmlsoap.org/ws/2005/07/securitypolicy/IncludeToken/Never">
<wsp:Policy>
<sp:WssX509V3Token10 />
</wsp:Policy>
</sp:X509Token>
</wsp:Policy>
</sp:RecipientToken>
<sp:AlgorithmSuite>
<wsp:Policy>
<!-- sp:Basic256/-->
<sp:TripleDesRsa15 />
</wsp:Policy>
</sp:AlgorithmSuite>
<sp:Layout>
<wsp:Policy>
<sp:Lax />
</wsp:Policy>
</sp:Layout>
</wsp:Policy>
</sp:AsymmetricBinding>
<sp:Wss10
xmlns:sp="http://schemas.xmlsoap.org/ws/2005/07/securitypolicy">
<wsp:Policy>
<sp:MustSupportRefKeyIdentifier />
<sp:MustSupportRefIssuerSerial />
</wsp:Policy>
</sp:Wss10>
</wsp:All>
</wsp:ExactlyOne>
</wsp:Policy>
<!--End of Endpoint Policy-->
<!--Message Policy1-->
<wsp:Policy wsu:Id="Sign_message_policy"
xmlns:wsp="http://schemas.xmlsoap.org/ws/2004/09/policy"
xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
<wsp:ExactlyOne>
<wsp:All>
<sp:SignedParts
xmlns:sp="http://schemas.xmlsoap.org/ws/2005/07/securitypolicy">
<sp:Body />
</sp:SignedParts>
</wsp:All>
</wsp:ExactlyOne>
</wsp:Policy>
<!--End of Message Policy1-->
You then reference these policies in the binding part of the WSDL. Example:
<binding name="ExampleServiceSOAP" type="foobar:ExampleServicePort">
<!-- WS-Security -->
<wsp:PolicyReference URI="#Endpoint_policy" />
<soap:binding style="document" transport="http://schemas.xmlsoap.org/soap/http"/>
<operation name="getSomething">
<soap:operation soapAction="getSomething" style="document"/>
<input>
<!-- WS-Security -->
<wsp:PolicyReference URI="#Sign_message_policy" />
<soap:body use="literal"/>
</input>
<output>
<soap:body use="literal"/>
</output>
</operation>
</binding>