Hi, have you tried deleting the users *.oab files? Haven't time to read all the thread but I have had issues with cached mode clients and the address book. go to
C:\Documents and Settings\users_username\Local Settings\Application Data\Microsoft\Outlook
and delete all the .oab files. I personally make a backup folder and put them in there.
This may not solve your problem but will rule it out of the equation!