Outlook is trying to retrieve data from Mail Server

Everyday end-users get the (in)famous ‘Outlook is trying to retrieve data from Exchange Server servername’.

We are using Outlook 2003 and Exchange 2003.

I have read in many places that this is the result end-users having more than the MS recommended number of emails (between 3,500 and 5,000) in a single folder.

Has anyone else read the same thing? Has anyone applied a different solution to the problem?

Thank youl.