Microsoft Outlook connection

Microsoft Outlook client does not connect to Exchange Server and pops up an error saying “Err-Client access Licenses not available” though we have only 50 clients whereas the CAL are 100.
The problem seems to vanish for sometime after revoking the licenses,only to return soon again.

Kindly suggest