This problem has been largely solved by WS-Trust, at least for SOAP-based web services anyway. WS-Trust is a well-defined protocol for validating and exchanging "authentication tokens", and can be used in cross-enterprise scenarios with protocols such as WS-Federation that are built on it.
One example scenario is to have the clients request a token from the WS-Trust server, then include that token in the SOAP header to the web service host. The flip side is to include something simple like <UsernameToken> in the request to the host, and have the server-side delegate authentication to the WS-Trust server.
There's pretty good client support for WS-Trust -- WCF has support out of the box, and various vendors have J2EE interceptors for JAX-RPC and JAX-WS web services.
While WS-Trust's focus is on authentication, you can do coarse-grained authorization by using logic about when to issue or validate a received token. Don't issue/validate the token, and access is effectively denied. Fine-grained authorization for web services will usually require some custom interceptors, which are vendor-specific.
I work for IBM Tivoli Security, and we have a few products in this space. The first is Tivoli Federated Identity Manager (TFIM). A colleague and myself wrote this article on integrating TFIM with WSE-based web services, and includes an overview of the WS-Trust protocol itself. The second product is Tivoli Security Policy Manager (TSPM), which implements fine-grained authorization for web services.
There are open source implementations of these same protocols, which is the upside of using a standards-based solution. I believe JBoss and WSO have implementations that might be useful.