From Julio:

I recently installed a new server running Windows 2008 R2 (as a DC) and the related computers running Windows 7 Pro. The computers are joined to the domain. In a computer, which is shared by two users (userA and UserB), I see the following event on the Event Viewer while userA was logged on:

Event ID: 45058
Source: LsaSrv
Level: Information

Description:

A logon cache entry for user userB@domain.local was the oldest entry and was removed. The timestamp of this entry was 11/14/2012 08:49:02.

All is working fine. Both userA and userB are able to logon on the domain by using this computer. Do you think I have to worry about this message or can I just safely ignore it?

FYI, our users never work offline, only online.

This event is typically caused by one of two things:

  1. You've lowered the CachedLogonsCount value on the client to 1 (or 2 and you're logging on with a smartcard)

    *or*

  2. You have a service, driver or application running on the client that's eating the other cached logon entries.

If you're only seeing the entry for UserB removed when logging on as UserA (and vice versa) then the first is the most likely catalyst.  After the logon succeds it needs to be cached, if there's not enough unused cache entries left then the oldest one will be removed and Event ID 45058 will be logged.

If you're never logging on offline then this can typically be safely ignored, for a laptop that's offline you would on the other hand not be able to log on offline as the user whose entry was removed.


Further details: 

Cached User logon fails when LSASRV event 45058 indicates FIFO deletion of cached credential
http://support.microsoft.com/kb/2555663