|How are you connecting to the server? Via POP3 or via IMAP?|
If POP, check the last tab on the account settings and there should be a message retention selection that tells it to delete messages after retrieval.
Because you are getting an error and it is not retrieving all of the messages, it may be causing the server not to delete any of them. Have you ever been able to retrieve all of the messages without getting an error? If not, there may be something else wrong with your settings.
Also, can you access the messages via web mail to the server and see if you can remove some messages that have already been downloaded to your local outlook PST from there.
Let me know if any of these suggestions work for you or if you need more assistance.
IT Desktop & Network Consultant - MOS Master Certified, MCP, MCSA, MCITP - Windows 7, CCNA Certificate Pending, A+, Network +