Normal Outlook Users:
Please follow the directions in this Microsoft article to resolve your issue - http://support.microsoft.com/kb/814441
Microsoft Exchange Users:
If you are using terminal services or remote desktop to check your emails on the server then you will need to make sure that Exchange is NOT running in cached mode. Please contact your server administrator to get this problem resolved.