It’s possible that they are resolving those disabled usrs via the offline address book and not via Exchange’s GAL. Try re-downloading the address book.
If they are running in cached mode and re-downloading the Offline Address Book does not work then have someone take their outlook off of cached mode and try again. Look through the event logs ont he server for OAB errors as well.
If the user id is still visible in the GAL for certain users then it is possible the GAL has not synced with the Information Store for those users since cached Exchange mode has a synchronization delay. Also, ensure that both the Exchange 2007 mailbox has been disabled along with the Active Directory account. 2007, as opposed to Exchange 2003 requires disabling both subjects in order to completely remove access to the mailbox. If only the AD account is disabled, it is possible that the user could still access their mailbox through Outlook Web Access.