Udi Dahan has just posted an excellent blog post about long running web services.
Recently while working on project I came across a similar sort of situation. In our scenario we were dealing with a web application calling and WCF based Web service which has some business logic execution steps followed by a call to a third party provider on http.
The B2B communication is handled by Tibco business works and we have noticed that performance is phenomenal, but business logic execution on our end uses SQL stored procedures and calls to some class library functions which has been a major bottle neck.
To get around this problem of waiting UI we decided to split the call to the WS into major sections - Submit request return to UI and then finally try to get a response back.
This approach more or less looks like Basic polling that Udi has mentioned in his post. I will try to implement REST-full polling that Udi has mentioned.