I had this problem many times. I completely removed all proxy access on both users then ran GWcheck (assuming your using GW 5.5 or better)structure and then contents. I also reset their client options to be safe. (Don't forget that this whacks the path to their archives if set). I then restored their proxy configurations, making sure to select using the address book, not just typing in the username and it seemed to be o.k. after that.
Good luck..
Janis