My customer is on a domain with her laptop. When she leaves the office with her laptop, goes home, connects to the laptop with her domain profile (not on the domain), logs into Windows, opens up her VPN to her office, and then opens Outlook. At this point, her Outlook doesn't remember her auto-completed names in Outlook, but if she closes Outlook and then goes to restore her NK2 file on her network profile on the server (its shared out over the network, so she can access it while on her VPN) to her profile\application data\microsoft\outlook\, the auto-complete works again.
Any idea why this might be happening? Sounds to me like something is corrupting the nk2 file itself.