I have finally found a solution to this problem on our system.
In the properties of my mailbox store, in Exchange 2000, "full text indexing" was scheduled to run every hour. This was running for 35 minutes of every hour during which the "requesting data" message constantly appeared on client machines throughout the office. I have changed the indexing to run once every morning at 5am and since then I have not seen one instance of the dreaded "requesting data message".