Licensing issue

Periodically we receive messages in our NT4 Server Event Viewer stating we are out of licensing for our Exchange 5.5 Server. When I check License Manager within NT4, the Clients (Per Seat) is showing many users that are no longer with the company. They have been removed from User Manager for Domains and Exchange Administrator, although they appear within License Manager. I revoke their licenses, although every week they come back and cause our licenses to exceed the purchased amount. Any suggestions?