Aha! More fodder for discussion:
…the identity information needs to be synchronized before the user performs his first authentication.
Why?  Why must identity information be synchronized before the user performs the first authentication? If a new employee has been provisioned an account at an IdP, why shouldn’t that person be able to arrive at a Relying Party, and at that time have the IdP advise the Relying Party that (1) the user is valid, and (2) the user should be provisioned into the system?    I don’t see why my example from earlier can’t work in reverse — you batch update your incoming staff updates, but if they attempt to access the system before the batch job is accomplished, the IdP bundles a specific real-time provisioning request into the authentication, and the user is set up and granted access.
To me, real-time back-end data synchronization is needed between silos. Once you have a single Identity authority with a reach across administrative domains, and once you are doing more than testing possession of a shared secret, you have alternatives. Perhaps not in every case – but in some cases, perhaps many cases. Imaginative exploration of these new usage models are what makes this technology so much fun!
The whole thing about federated identity: one should keep ‘context’ in mind. The user *doesn’t authenticate* to the relaying party. The relying party get’s proof of ‘authenticated identity’. So in the context of the relying party there really never is a “first authentication”.
With that in mind your example works well. And is, afaik, in accordance with european privacy law.
Speaking from the view of one who deals with the replication of information between silo’s I couldn’t agree more. This is a legacy way of thinking based on current AuthN processes. There is no reason why the concept of AuthN/AuthZ will not/should not evolve such that valid identities are synchronized or provisioned on demand. However, this does bring up the subject of abuse as it would potentially expose a new attack surface if the appropriate controls are not in place. If I have the ability to flood the request channel with bad AuthN requests then I could compromise the channel between the RP and the IdP as the RP faithfully attempts to check for object that require on demand provisioning.