An error occurs in the Exchange event log stating that my customers are out of licenses when clearly they are not. How come?
Since they have enough legal licenses, disable the Licensing service. I know that sounds odd, but frankly the problem you describe is very common and the conventional wisdom among Exchange administrators is that the License Logging service is more trouble than it’s worth.
Go to Start | Settings | Control Panel | Services on your Exchange Server, find the License Logging service, and change its startup setting to Manual or Disabled. Then restart your server (at your convenience), and the problem will go away.
If they didn’t have enough licenses the solution would be more obvious: buy more licenses.