the only bit of information a browser could keep is cookies which are limited by domain.

A browser can also send get/post parameters, which is the usual way to keep session when cookies are disabled. Thus, if the service receives a token as a means for user authentication, each time it generates a link to another service it should add a token to it. For instance, http://other-foo.com would become http://other-foo.com?token=xxx.

On the other hand, sharing secret keys is obvious to be expected in any scenario in order for each "service provider" to be able to communicate (securely) with the "login server".

I would rather use a public key crypto scheme and share public keys rather than secret keys. This allows confidentiality during information exchange without requiring a previous confidential channel for key exchange and lets you keep each private key in a single location, thus reducing leakage risk.

if done locally, people could get "stalled" access

Would you really need real-time authorization changes? I would let services poll the authorization server every now and then (say half an hour) to check if any authorization has changed and in that case invalidate all sessions for no-more authorized clients. This would be totally transparent to the user and would not require much network traffic or impose delays in navigation, while still keep the system quickly responsive to authorization changes.

Cheers

Antonio Bellezza