Assuming you mean a Windows Forms application when you say "windows based
application", and assuming the webservice is not dependent on the WinForms
app
being present, you could use ClickOnce. Deploy the webservice as a
prerequisite
using the Bootstrapper, and deploy the application using ClickOnce.

The prerequisite can be a .exe installation package, or msi, or even just a
.Net program you want to run. You can use the bootstrapper manifest
generator
to add your own entries to the prerequisite list in Visual Studio.

The other thing we have considered is to include the webservice installation
in the application deployment, and then have the application actually
check for the necessity to install the webservice and do so if needed.

Good luck.
Robin S.
GoldMail, Inc.
-------------------