Richard,
This may be related to the fact that when a user logs into the Service Client, it downloads a set of information based on what that user has access to. It's possible that when you create a new user in the Admin Center with OCO enabled (a BPOS license for example), that there is a propagation time for our domain controllers (I cannot give an exact time for propagation, but I would estimate up to 15 minutes) to update with all services this user has access to.
If the user attempts to configure their applications through the Service Client before this is propagated, they could get the configuration without OCO. The client doesn't automatically go back to the server to get the new configuration data. It can take up to 72 hours for this to happen as it is tied to cert download.
However, logging off and back in forces the client to refresh the data from the server.
If you have attempted this already, and if this issue is reproducible, I would highly suggest contacting Technical Support using this information: http://technet.microsoft.com/en-us/library/cc742651.aspx so that we can investigate and resolve this issue, as this may not be simply an issue of the Service Client needing to refresh the certificate after an expected 15 min propagation time, but rather an unexpected propagation issue on our server.
Hope this helps,
Justin Bakelaar – BPOS Support