Outlook Keeps on Error Messaging of Deleting Message

In our network, we are using Windows XP Pro Special Pack 3. An error message is showing in a lot of workstations which says: “Outlook Express have to delete messages to clear the space”. Even if it seems not a big issue some of users are getting annoyed by this message. If anybody knows how to solve issue, please let me know.
