Users can’t delete emails out of Outlook

We recently upgraded from Exchange 5.0 to 5.5 and now none of the users can choose “delete all emails and subdirectories in the Deleted Items folder” without Outlook hanging. Users can, however, delete each email separately, by selecting it and deleting manually.