Cannot login with cached credentials when laptop is locked and off the network

Please bare in mind that by default, Mac OS X Bonjour services use the .local domain for mdns resolution.

Obviously, this conflicts with the windows AD default domain of .local also as Mac OS X will not use the domain controller as it's DNS server when trying to resolve .local domains.

The simplest solution is to use the IP of the Active Directory in Directory Utility instead of the name.

To do this, go to  > System Preferences > Accounts, click "Login Options" then click on "Join" next to "Network Account Server:".

In here you can open Directory Utility by clicking the "Open Directory Utility" button, then click on "Active Directory" and then the pencil icon. Here you can change your AD server to the IP of the Domain Controller instead of the name.

This should speed up the login process considerably.

Of course, the other option is to change the .local domain to something else like .internal, but this is only helpful when setting up a new domain. Infact it's mentioned in the Microsoft SBS server handbook.

As the comments suggest, your problem is that you have more users logging on than you have credentials being cached, so some of those credentials you want cached are being overwritten by more recent logins.

Up the number of cached credentials and the problem should go away. This can be controlled by GPO on the domain, or local security policy. Either way, you open up the policy editor, navigate to Computer Configuration -> Policies -> Windows Settings -> Security Settings -> Local Policies -> Security Options and edit Interactive logon: Number of previous logons to cache (in case domain controller is not available).

By default, it's 10, set to at least the number of accounts you'll have logging on, and that should take care of the problem.