We had a problem a few days ago with exactly the same message. We were trying to set up a Smartner Duality client on a PocketPC, and it just wouldn't connect to the Exchange Mailbox without reporting an error.
After some investigating, we thought that there may be some problem with the mailbox itself, so we decided to create a PST file and move everything over. We were then going to create a new mailbox for the user and transfer everything back in. Unfortunately, every time we tried to move the messages across, we got the error message displayed as you described above. It also came up if we tried to use the 'export' function.
In the end we dragged across a few at a time until all messages were across. Some wouldn't copy at the first attempt, but would on the second. Some would only copy if they were individually selected.
When we created the new mailbox, and dragged them all back, everything worked as expected, with all messages intact. The Smartner Duality client also then connected as it should.
I have to assume that there was some form of corruption in the mailbox, which could only be resolved by creating a new one.
Hope this helps.
Rik