Hai ragione... Non so come mai mi è venuta da suggerirti la soluzione ASP.NET :bubu:
Cmq la chiamata asincrona al web service è uguale anche nel caso di Windows App e ti permette sempre di poter proseguire con la tua applicazione per mostrare un messaggio di attesa o una ProgressBar.
Il problema della ProgressBar è che non sai quanto può durare al massimo la chiamata al web service... Giusto?

HTH