Don't rely on auto generated exceptions across service boundaries! Do use the @WebFault annotation you were considering. If the client will ever need to deal with it, there is nothing exceptional about it. Make it part of your data contract(Fault Contract). Google "SOAP fault element" there are tutorials and other articles explaining how and why.
The normal control flow in the service should deal with fault situations... faults are not necessarily exceptional.
When it comes to throwing exceptions here are some great "almost" rules for exceptions (of course there are exceptions to these rules):
Almost Rule #1
When deciding if you should throw an
exception, pretend that the throw
statement makes the computer beep 3
times, and sleep for 2 seconds. If
you still want to throw under those
circumstances, go for it.
Almost Rule #2
If you think it will be at all normal
for anyone to want to catch your
exception, then probably it shouldn't
be an exception at all.
When you apply these to a service request/exchange you see that it really doesn't make sense to think in terms of exceptions coming back to the caller. If the caller is ever going to be told about a problem, there is nothing truly exceptional about the problem at that point, and it should be handled by the service contract.
Even if you just have one fault contract that says "the request failed for an unknown reason" the client can anticipate that and it becomes part of the contract. If you want to get more detailed as necessary, it might be helpful depending on your requirements.
Think of the REST service architecture. Http returns a handful of pre-defined error codes. There are just enough different error categories that the client can take appropriate action for each... give-up because the resource (page) is gone permenantly, redirect because the page has moved, retry because there was an internal server error, deal with user for permissions required, etc. As a general http client, you wouldn't expect to see internal language exceptions come back and mean anything to you. There are dozens of languages, and thousands of potential exceptions in existing http service implementations. That's why they aren't part of the contract.
Hopefully that helps explain why your faults are not exceptional, and why the should be an explicit part of the contract.
Good luck-