I got one positive and one negative to Async service calls versus a new
thread.  

Positive: Asnyc calls allow you to "cancel" a web service call.  Granted it
does not save the server from doing the work, but at least it gives you a
means to interact from the UI.  For instance, if you are calling a webmethod
that performs a lengthy search, but want to cancel it.... Async makes that
nice and clean on the client side (just make sure to handle the web exception
in the callback method :P

Negative.  Overloading.  I like to use overloaded methods becuase it makes
my intellisense nice and neat :)  WebServices accomidate this by letting you
assign a MessageName attribute to the method so that for the service it has a
unique name, but your proxy will overload it ias normal.  The downside to
this is that for Begin .. End methods that get created are just numbered.  
BeginSearch1, BeginSearch2, etc.   That just plain sucks, and I can only
assume it will "renumber" them if you add new methods.  I am not even sure
what logic it uses to get the numbers :)

Anyway, interesting topic.

John