License problem on NT

Every once and a while I get a message in the event log saying my NT Server is out of licenses. When I check the license administrator it shows that some of my licenses have been consumed by users who have been deleted from User Manager. I delete the license from license administrator and after awhile the same deleted user consumes a license. Any help would be appreciated.