Usage Alerting Service is Unavailable

Recently we regularly run into the following problem:

We encounter a very slow start-up of the CONNECT Licensing applications MicroStation and Bentley View. Users have to wait for about 2 minutes !! before the message as shown above appears.
What can be the cause of this?