It happens that I get a question on how to call webservices in an asynchronous manner. It is actually not that hard, even the tools does not support this out of the box (or so it seems ;-)).
To generate a proxy that supports the async-pattern (Begin<method>/End<method>); you have 2 directions to go:
You can use the svcutil.exe utility from WCF. The syntax is this:
svcutil.exe /async <url to wsdl-file> (this is the most basic form! More advanced versions exists)
2) VS service reference
Visual Studio does actually support this behavior if you are a bit careful when generating the proxy. If you check this box, you do get methods named Begin<method>/End<method>.