Don't you have an employee table that lists the AD login and whether the
employee is active or not?  Some companies store this data directly in AD.  
You need to find out where the information is stored though, before we can
tell you how to fix your issue.

Another question...are they disabling the AD account?  If you were using AD
groups, instead of individual logins, you would no longer have to worry about
an individuals access.  It's also easier to manage and delegate management
responsibility to the business and HR.

I found the sp_ValidateLogins very helpful.  
To quote the BOL - "Reports information about orphaned Microsoft® Windows
NT® users and groups that no longer exist in the Windows NT environment but
still have entries in the Microsoft SQL Server™ system tables."

Randy