NT Server out of licenses after reboot

I get an event notice telling me the server (NT & Exchange) is out of licenses after I reboot the server. The problem is that past employees reappear on the license mgr, even after I’ve revoked and deleted their licenses.

Lets say I have 100 NT client and Exchange licenses, 110 employees but 20 come and go. No more than 100 licenses was used at any time. Now have total of 90 users. Deleted 20 users from License and User Mgr. Now under License Mgr, it shows 90 NT client and Exchange licenses used. Reboot server, all previous deleted users show up on License Mgr. Now I’m 10 licenses over. Of course I just go and delete the unused licenses again.

Is there a step I’m missing to permanently delete old licenses?