Getting a pop-up that says “trying to retrieve data from exchange server”

We have remote office with 10 users
When they using MS Outlook 2007
constantly getting a pop-up that says “trying to retrieve data from exchange server” and they cannot work until they close the popup which will come back approximately 40 or 50 min.

Before we had our own Exchange server , two week ago we start outsourcing our email , basically all our email has been managed by the different company now.

Also would like to add that>
|_>> All users running under cache mode
All Outlook clients running with SP2

Any ideas?

Please let me know.