My company is running one exchange server for multiple off site clients that we connect to via GRE Tunnels. One of our clients is seeing anothers GAL in Outlook. I have tried taking Outlook out of Cached mode, the correct GAL appears in the address book, but when I place back in cached mode, the wrong GAL appears again. If I rebuild profiles for the users, the correct GAL appears in the address book, but am hesitant to do this because this is a fairly large client (50 Users) and it is very time consuming. Any Ideas?

Try disabling cached mode for that user, then move the OST file to a new location and re-enable cached mode to using a uni-code based ost file as opposed to an ansi one. Set outlook to download headers first then emails so that while synchronization is in progress the user will still be able to continue working. See the following article regarding Chached mode and Offline Address Book: http://office.microsoft.com/en-us/ork2003/HA011402591033.aspx