When adding a service reference, Microsoft Visual Studio 2008 only generates synchronous method calls to the services. You can easily change this by clicking the Advanced button, and...
...checking the Generate asynchronous operations checkbox.
It now generates the Begin*, End* and *Async methods for you to call from your application.
If you've already added the service references, you do not have to remove-and-add them to generate the asynchronous proxy methods - instead, right click the service reference and select "Configure Service Reference".