Been having this problem on all machines which use Cached Exchange Mode at work. Was really beginning to get annoying as any of the suggestions that I found on the MSExchange Team blog did not seem to work. For reference, the site is was on is: http://msexchangeteam.com/archive/2007/04/19/437902.aspx
After a while of head scratching and null answers, started looking a bit out of the box. Had a look at ISA server, just by chance, and noticed an error occurring every time that a Send/Receive was initiated from a client.
As my ISA server is only meant to log internet requests, I thought this was a bit weird. A look a little closer found that I had a typo in an address configured in my proxy pac file. All local traffic had been going to my ISA server and being logged since I made the change (about a week ago).
So, sorted out my proxy pac file, made sure that everything was pointing to the right place, and everything started ticking along nicely.
Downloads started working and everyone could then access the address list offline again.