Use a SSL certificate on your web service as any data passed to this is encrypted.
An encrypted SSL connection requires
all information sent between a client
and a server to be encrypted by the
sending software and decrypted by the
receiving software, protecting private
information from interception over the
Internet.
Also on every call to the service send up a single guid that you have defined along with your data. This guid has to be validated before the web service performs any action. To lock down even further you can create a service that generates a guid which needs to be passed back up for any subsequent calling service.
Also make sure you don't allow anybody to see your wsdl on the server else they can guess your parameters.
A SSL ceritifcate from RapidSSL costs $17 a year so the cost is nothing to worry about.