Well, for the short answer of is it thread safe, is yes. The reason is that the server side of the service will have more to say then the client connection as to threading capabilities. The client is just a proxy that lays out the request in a fashion that the server can understand. It knows nothing. It is a basic class, no outside access other than the connection to a server. So as long as the server allows multiple connections you would be fine. Thus no resource contention (Except for the server being able to handle all your requests).
On the client side you can have multiple threads use the same class but different instances. This would probably be the preferred scenario so that each transaction can be atomic. Whereas the shared instance you would have to handle your own thread locking around the access of the class itself otherwise you may run into a race condition on the resource internal to your code.
There is also the ability to have a asynchronous call. The stubs generated by wsdl tool will create the begin, end invoke methods so that you can provide a callback method to effectively allow you to submit your request and continue your code without waiting for a reply. This would probably be the best for your second scenario with the single instance.
However it also depends on how the server component is coded. If it's a webservice you should be able to submit multiple requests simultaneously. However if it's a socket based service you may need to do some additional coding on your end in order to handle multiple incoming connections or even to create sockets for example.
So in short yes the different instances behave the same as single threaded execution within the limits of the server side being able to handle multiple concurrent connections.
As for the single instance if you use a callback process, which is provided you may be able to get what you are after without too much headache. However it is also restricted to the limits of the server side code.
The reason I state the server limits is that there are companies that will build webservices that restrict the number of connections coming from outbound hosts so your throughput is limited by this. Thus the number of effective threads you could use would be reduced or made obsolete.