OAB - Address List changes not visible in Outlook clients


We recently moved from an inhouse Exchange server to a hosted Exchange
Server 2007 solution.

The users in the office still login to a local domain for other apps (server
will be shutdown shortly) and are using Outlook Anywhere to connect to the
external Exchange 2007 server.

I started setting up some test Address Lists and I noticed that the users do
not see the changes in Outlook 2007 - even after they manually select to
download the address book changes. What's interesting is that the one Vista
PC in the office shows the correct Address Lists but none of the XP pro
computers see the changes - all using Outlook 2007.

"Enable Web-based distribution" is set-up on the server.

When a user also clicks on other default address lists - e.g. "All Groups" -
they receive this message:

"The address list cannot be displayed. The connection to Microsoft Exchange
is unavailable. Outlook must be online or connected to complete this action."

Hope someone has come across this one and has a solution! :-)