First of all, I would disagree with this statement:
Favour exceptions over error codes
This is not always the case: for example, take a look at Objective-C (with the Foundation framework). There the NSError is the preferred way to handle errors, despite the existence of what a Java developer would call true exceptions: @try, @catch, @throw, NSException class, etc.
However it is true that many interfaces leak their abstractions with the exceptions thrown. It is my belief that this is not the fault of the "exception"-style of error propagating/handling. In general I believe the best advice about error handling is this:
Deal with the error/exception at the lowest possible level, period
I think if one sticks to that rule of thumb, the amount of "leakage" from abstractions can be very limited and contained.
On whether exceptions thrown by a method should be part of its declaration, I believe they should: they are part of the contract defined by this interface: This method does A, or fails with B or C.
For example, if a class is an XML Parser, a part of its design should be to indicate that the XML file provided is just plain wrong. In Java, you normally do so by declaring the exceptions you expect to encounter and adding them to the throws part of the declaration of the method. On the other hand, if one of the parsing algorithms failed, there's no reason to pass that exception above unhandled.
It all boils down to one thing:
Good interface design.
If you design your interface well enough, no amount of exceptions should haunt you.
Otherwise, it's not just exceptions that would bother you.
Also, I think the creators of Java had very strong security reasons to include exceptions to a method declaration/definition.
One last thing: Some languages, Eiffel for example, have other mechanisms for error handling and simply do not include throwing capabilities. There, an 'exception' of sort is automatically raised when a postcondition for a routine is not satisfied.
The cost of throwing an exception is negligible compared to writing to a disk. In addition, return codes are more expensive, not less. Finally, nobody is going to care how fast your library is when they can't make their program have the correct semantics because their teammate who just joined the company forgot to check a return code.
The only safe return code is the one that the user can safely ignore.
Best Answer
SOAP has a concept of faults, you can convert an exception to a fault on the server side and on the client proxy the fault can again be converted back to an exception. This works remarkably well in WCF and Java metro stack, cannot comment on native C++ clients.
As regards to SOA best practice define one generic fault and few specific faults only if the client need to handle a certain type of error differently. Never send a exception stack trace to client in production deployment. This is because in theory the server trace has no meaning for the client and for security reasons as well. Log the full error and stacktrace on the server and send a unique reference to the log in the fault. In WCF I use the Microsoft Exception Handling block from Enterprise Library to generate a guid and also convert a exception to SOAP fault.
Check the guidance at Microsoft Patterns and Practices.