Question : Outlook cache does not retain data

One of our users is unable to write to his nk2 file.  The addressee cache remains only in temporary storage, and once he restarts, the cache is lost.  I went to look at his cache file, and it wasn't even there.  

So I changed the permissions on the Outlook directory to remove any read only attributes, opened Outlook, addressed a message, closed Outlook, and the file appeared.  However, that change is the last that has happened to the file.  It is not updating.   I verified that he has permissions on the file.

Original question below (he was given an entirely different system following the list of attempts to remedy below):
We are in an Exchange 2003 environment with Windows XP Pro and Outlook 2003.

We have a partner who recently acquired a Dell Latitude D620.  This is a relatively new laptop as it was bought in the last year.  It has had one prior owner, and it was given a fresh image prior to assignment.  The user indicates that ever since he received the laptop, his Outlook cache randomly drops addresses.  I tested and verified this myself.  I could send to one address, restart, and the address would still be in cache.  I would send to another address, restart, and the address would not be in cache.  

We tried deleting the Outlook file that contains this data (I forget which one it is off the top of my head).  That didn't work.  We tried deleting frmcache.dat (just because it seems to be the fix it all for Outlook).  That didn't work.  We recreated his profile.  We had him not run various programs.  We recreated his profile.  We built a new image for the laptop and redid the whole thing.  The issue still persists.

I started thinking this might be coming down from his Citrix profile, as he does not have a roaming profile to consider.  However, he indicates today that his Hearts game also lost his stored name.  

Please advise.

Answer : Outlook cache does not retain data

It turns out that Zeacom's Desktop Voicemail is the culprit.  It can be configured to read Outlook contacts, and when it is so configured, it does not release Outlook from memory.  The user was closing Outlook first, then shutting down.  Since Zeacom's app left Outlook open, that did not give Outlook a chance to write the cache file before the system terminated.  

The user is now closing Desktop Voicemail first, then Outlook, and the cache is successfully writing.  We've submitted a bug fix request to Zeacom.